[cpp]
#include
#include
#include
#define maxsize 110
int s[maxsize][maxsize];
int main()
{
int n,m,i,j,k,time;
scanf("%d %d",&n,&m);
while(n!=0||m!=0)
{
for(i=0;i
for(j=0;j
s[i][j]=INT_MAX;
for(k=0;k
{
scanf("%d %d %d",&i,&j,&time);
s[i-1][j-1]=time;
s[j-1][i-1]=time;
}
for(k=0;k
{
for(i=0;i
{
for(j=0;j
{
if(s[i][k]==INT_MAX||s[k][j]==INT_MAX)
continue;
else
if(s[i][k]+s[k][j]
s[i][j]=s[i][k]+s[k][j];
}
}
}
printf("%d\n",s[0][n-1]);
scanf("%d %d",&n,&m);
}
}