最短路

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=205;
const int inf=0x3f3f3f3f;
int map[maxn][maxn];
int dis[maxn];
int vis[maxn];
int main(){
    int n,m,a,b,c;
    while(cin>>n>>m){
        if(!n&&!m) break;
        memset(vis,0,sizeof(vis)); 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) map[i][j]=0;
                else map[i][j]=inf;
            }
        }
        for(int i=0;i<m;i++){
            cin>>a>>b>>c;
            map[a][b]=c;
            map[b][a]=c;
        }
        for(int i=1;i<=n;i++){
            dis[i]=map[1][i];
        }
        vis[1]=1;
        for(int i=1;i<=n-1;i++){
            int min=inf,z; 
            for(int j=1;j<=n;j++){
                if(!vis[j]&&dis[j]<min){
                    min=dis[j];
                    z=j;
                }
            }
                vis[z]=1;
                for(int k=1;k<=n;k++){
                    if(map[z][k]<inf&&map[z][k]+dis[z]<dis[k])
                    dis[k]=map[z][k]+dis[z];
                }
        }
        cout<<dis[n]<<endl;
    }        
}