#include"iostream"
#include"cstdio"
using namespace std;
int h[100];
int u[100];
int v[100];
int w[100];
int first[100];
int next[100];
int n,m;
int size;
int book[100];
int dis[100];
int pos[100];
int sum=0;
int count=0;
int inf=999999999;
void swap(int x,int y) //pos数组记录的是顶点在堆中的编号
{
int t;
t=h[x];
h[x]=h[y];
h[y]=t;
t=pos[h[x]];
pos[h[x]]=pos[h[y]];
pos[h[y]]=t;
}
void siftdown(int i) //这里我们的下沉和上移函数的判断标准是dis数组的大小
{
int t,flag=0;
while(i*2<=size&&flag==0)
{
if(dis[h[i]]>dis[h[i*2]])
{
t=2*i;
}
else
{
t=i;
}
if(i*2+1<=size)
{
if(dis[h[t]]>dis[h[i*2+1]])
{
t=i*2+1;
}
}
if(t!=i)
{
swap(i,t);
i=t;
}
else
{
flag=1;
}
}
}
void siftup(int i)
{
int flag=0;
if(i==1)
{
return ;
}
else
{
while(i!=1&&flag==0)
{
if(dis[h[i]]<dis[h[i/2]])
{
swap(i,i/2);
i=i/2;
}
else
{
flag=1;
}
}
}
}
int pop() //弹出堆顶的元素，返回堆顶的编号
{
int t;
t=h[1];
h[1]=h[size];
size--;
pos[h[1]]=1;
siftdown(1);
return t;
}
void prepare() //前期准备函数
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u[i],&v[i],&w[i]);
}
for(int i=m+1;i<=2*m;i++) //因为是无向图，我们必须要进行双向存储