学步园

#include<cstdio>
#include<cstring>
const int Max(1000000);
int map[105][105],dis[105];
bool vis[105];
int Dijkstra(int v,int n)
{
	int i,j,cur;
	memset(vis,0,sizeof(vis));
	for(i=1;i<=n;i++)
		dis[i]=map[v][i];
	dis[v]=0;
	vis[v]=1;
	for(i=1;i<=n;i++)
	{
		int min=Max;
		for(j=1;j<=n;j++)
			if(!vis[j]&&min>dis[j])
			{
				cur=j;
				min=dis[j];
			}
		if(min==Max)
			break;
		vis[cur]=1;
		for(j=1;j<=n;j++)
		if(!vis[j]&&dis[j]>dis[cur]+map[cur][j])
			dis[j]=dis[cur]+map[cur][j];
	}
	return dis[n];
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m),n||m)
	{
		int a,b,c;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				map[i][j]=Max;
		while(m--)
		{
			scanf("%d%d%d",&a,&b,&c);
			map[a][b]=map[b][a]=c;
		}
		printf("%d\n",Dijkstra(1,n));
	}
	return 0;
}