思路

无向图含重边/零权/自环，1到n不可达-1，N2000/M10000，最短路非生成树。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<vector<pair<int,int>>>g(n);while(m--){int a,b,c;cin>>a>>b>>c;g[--a].push_back({--b,c});g[b].push_back({a,c});}vector<long long>d(n,LLONG_MAX/4);priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;d[0]=0;q.push({0,0});while(!q.empty()){auto p=q.top();q.pop();if(p.first!=d[p.second])continue;for(auto e:g[p.second])if(d[e.first]>p.first+e.second){d[e.first]=p.first+e.second;q.push({d[e.first],e.first});}}cout<<(d[n-1]==LLONG_MAX/4?-1:d[n-1])<<'\n';}