poj2387-Til the Cows Come Home

//#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=1010;
const int maxm=2020;
const int inf=0x3f3f3f3f;
int e[maxn][maxn];
int book[maxn],dis[maxn];
int n,t;
int a,b,c;
int main(){
    cin>>t>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){           
            if(i==j)e[i][j]=0;
            else e[i][j]=e[j][i]=inf;
        }
    }
    for(int i=1;i<=t;i++){
        cin>>a>>b>>c;
        if(c<e[a][b])
            e[a][b]=e[b][a]=c;
    }
    for(int i=1;i<=n;i++){
        book[i]=0;
        dis[i]=e[1][i];
    }
    book[1]=1;
    int u;
    for(int i=1;i<=n-1;i++){
        int min=inf;
        for(int j=1;j<=n;j++){
            if(book[j]==0&&dis[j]<min){
                min=dis[j];
                u=j;
            }
        }
        book[u]=1;
        for(int v=1;v<=n;v++){
            if(e[u][v]<inf)
                if(e[u][v]+dis[u]<dis[v])
                    dis[v]=dis[u]+e[u][v];
        }
    }
    cout<<dis[n]<<endl;
    return 0;
    
}