SPFA

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
const int inf=0x3f3f3f3f;
int n,m;
struct node{
    int v,w;
    node(){ }
    node(int _v,int _w){
        v=_v;
        w=_w;
    }
};
vector <node> g[maxn];
int dst[maxn];
queue <int> qu;
int inq[maxn];

int add(int u,int v,int w){
    g[u].push_back(node(v,w));
    g[v].push_back(node(u,w));
}

void spfa(int s){
    memset(dst,inf,sizeof dst);
    int u=s;
    dst[u]=0;
    qu.push(u);
    inq[u]=1;
    while(!qu.empty()){
        u=qu.front();
        qu.pop();
        inq[u]=0;
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i].v;
            int w=g[u][i].w;
            if(dst[v]>dst[u]+w){
                dst[v]=dst[u]+w;
                if(!inq[v]){
                    qu.push(v);
                    inq[v]=1;
                }
            }
        }
    }
}

int main(){

    cin >> n >> m;

    int u , v , w;

    while (m--){

        cin >> u >> v >> w;

        add(u,v,w);}

    spfa(1);

    cout << dst[n]<<endl;

    return 0;

}