dijkstra
https://vjudge.net/contest/346398#problem/D
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define rep(i,x,y) if((x)<=(y)) for (register int i=(x);i<=(y);i++)
using namespace std;
int main()
{
bool vis[200];
int n,m,dis[200],a[200][200],t1,t2,t3,st;
while (1)
{
cin>>n>>m;
rep(i,1,n)
vis[i]=0;
rep(i,1,n)
rep(j,1,n)
a[i][j]=999999;
rep(i,1,n)
{
dis[i]=999999;
vis[i]=0;
}
if (n==0 and m==0)
return 0;
rep(i,1,m)
{
cin>>t1>>t2>>t3;
a[t1][t2]=t3;
a[t2][t1]=t3;
}
vis[1]=1;
dis[1]=0;
rep(i,1,n)
{
int minn=999999,temp=1;
rep(j,1,n)
if (!vis[j] and dis[j]<minn)
{
minn=dis[j];
temp=j;
}
vis[temp]=1;
rep(j,1,n)
if (!vis[j] and dis[temp]+a[temp][j]<dis[j])
dis[j]=dis[temp]+a[temp][j];
}
cout<<dis[n]<<endl;
}
return 0;
}