思路： 1寻找距离起点最近的点
2将该点加入集合
3用该点连边更新最短距离

#include<bits/stdc++.h>
using namespace std;

const int N=510,INF=0x3f3f3f3f;
int g[N][N],dist[N];
int n,m;
bool st[N];

int dijkstra(){
    memset(dist,INF,sizeof(dist));
    dist[1]=0;

    for(int i=0;i<n-1;i++){   
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[j]<dist[t]))   
                t=j;
        }
        //if(t==n) break;    可以加上，提前跳出循环
        st[t]=true;   

        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }

    }

    if(dist[n]==INF)  return -1;
    else return dist[n];
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) g[i][j]=0;
            else g[i][j]=INF;
        }
    }

    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }

    cout<<dijkstra()<<endl;
}