#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e3+2;
int n,m;
struct node{
	int id,w;
};
vector<node>e[MAXN];
int ans[MAXN],cnt[MAXN];
bool flag[MAXN];
bool operator < (node x,node y){
	return x.w>y.w;
}
priority_queue<node>q;
int main(){
	scanf("%d%d",&n,&m);
	memset(ans,0x3f,sizeof(ans));
	memset(cnt,0x3f,sizeof(cnt));
	cnt[1]=0;
	for(int i=1;i<=m;i++){
		int from,to,w1;
		scanf("%d%d%d",&from,&to,&w1);
		e[from].push_back({to,w1});
		e[to].push_back({from,w1});
	}
	q.push({1,0});
	while(!q.empty()){
		int x=q.top().id;
		q.pop();
		if(flag[x]) continue;
		flag[x]=true;
		for(node i:e[x]){
			if(cnt[i.id]>cnt[x]+i.w){
				ans[i.id]=min(cnt[i.id],ans[x]+i.w);
				cnt[i.id]=cnt[x]+i.w;
				q.push({i.id,cnt[i.id]});
			}else if(ans[i.id]>cnt[x]+i.w&&cnt[i.id]<cnt[x]+i.w){
				ans[i.id]=cnt[x]+i.w;
			}
		}
	}
	printf("%d",ans[n]);
	return 0;
}

输入：

5 10
1 2 3355
2 3 1712
1 4 4892
1 5 1442
5 3 4768
3 1 4334
2 1 4365
3 1 2591
2 1 3817
3 2 4068

正确输出：

4326

Mine:

7359