题解 | #【模板】单源最短路2#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let [n,m]=(await readline()).split(" ").map(it=>parseInt(it));
    let INF=+Infinity;
    let mat=new Array(5001).fill(0).map(()=>new Array(5001).fill(INF));
    while(m--){
        let [u,v,w]=(await readline()).split(" ").map(it=>parseInt(it));
        mat[u][v]=w;
        mat[v][u]=w;
    }
    let dist=new Array(5001).fill(INF);
    dist[1]=0;
    let vis=new Array(5001).fill(false);
    for(let i=1;i<=5000;i++){
        let x=-1;
        for(let y=1;y<=5000;y++){
            if(!vis[y]&&(x==-1||dist[y]<dist[x])){
                x=y;
            }
        }
        vis[x]=true;
        for(let y=1;y<=5000;y++){
            if(mat[x][y]==INF) continue;
            if(!vis[y]) dist[y]=Math.min(dist[y],dist[x]+mat[x][y]);
        }
    }
    console.log(dist[n]==INF?-1:dist[n]);
}()