dijkstra

#include<stdio.h>  
#include<string.h>  
#include<iostream>  
using namespace std;  
#define N 0x1f1f1f1f  
int w[151][151];  
int d[155];  
int ans,vis[151];  
int n,m;  
void Dij()  
{  
    int i,j,k,v,tmp;  
    memset(vis,0,sizeof(vis));  
    for(i=1;i<=n;i++)  
        d[i]=w[1][i];  
    d[1]=0;  
    vis[1]=1;  
    for(i=1;i<=n;i++)  
    {  
        tmp=N;  
        for(j=1;j<=n;j++)  
        {  
            if(tmp>d[j]&&!vis[j])  
            {  
                tmp=d[j];  
                v=j;  
            }  
        }  
        vis[v]=1;  
        for(k=1;k<=n;k++)  
        {  
            if(!vis[k])  
            d[k]=min(d[k],d[v]+w[v][k]);  
        }  
    }  
}  
int main()  
{  
    while(~scanf("%d%d",&n,&m))  
    {  
        if(n==0&&m==0)break;  
        for(int i=1;i<=n;i++)  
        {  
            for(int j=1;j<=n;j++)  
            {  
                w[i][j]=0x1f1f1f1f;  
            }  
        }  
        for(int i=0;i<m;i++)  
        {  
            int a,b,dis;  
            scanf("%d%d%d",&a,&b,&dis);  
            if(w[a][b]>dis)  
            w[a][b]=w[b][a]=dis;  
        }  
        Dij();  
        printf("%dn",d[n]);  
    }  
}