学步园

#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int , int> ll;
ll num;
int box[110],cnt;
struct node
{
	int e,next,w;
}side[20010];
void join(int s,int e,int w)
{
	side[cnt].e=e;
	side[cnt].w=w;
	side[cnt].next=box[s];
	box[s]=cnt++;
}
void init()
{
	int i,t1,t2,t3;
	cnt=0;
	memset(box,-1,sizeof(box));
	for(i=0;i<num.second;i++)
	{
		cin>>t1>>t2>>t3;
		join(t1,t2,t3);
		join(t2,t1,t3);
	}
}
void dij()
{
	priority_queue< ll, vector<ll>, greater<ll> >qq;
	int i,dis[110],j,k;
	bool vis[110];
	memset(dis,127,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	ll st(0,1),tt;
	qq.push(st);
	while(qq.size())
	{
		tt=qq.top();
		qq.pop();
		if(tt.second==num.first)
			break;
		vis[tt.second]=1;
		for(i=box[tt.second];i!=-1;i=side[i].next)
			if(!vis[side[i].e]&&dis[side[i].e]>dis[tt.second]+side[i].w)
			{
				dis[side[i].e]=dis[tt.second]+side[i].w;
				qq.push(make_pair(dis[side[i].e],side[i].e));
			}
	}
	cout<<dis[num.first]<<endl;
}
int main()
{
	while(cin>>num.first>>num.second)
	{
		if(num.first==num.second&&num.second==0)
			break;
		init();
		dij();
	}
}