eid[i]表示到这个点最短路的前一条边，pre[i]为前一个点，path保存到n的最短路的每一条边

#include "iostream"
#include "queue"
#include "cstring"
using namespace std;
int head[105], pre[105], eid[105], idx, n, m, ans1, ans2, temp1, temp2, temp3, dis[105], path[10005], pi;
int edited_id, edited_w;
bool book[105];
struct edge{
	int to, nxt, w;
}e[10005];
void add_edge(int u, int v, int w){
	e[++idx].to=v;
	e[idx].w=w;
	e[idx].nxt=head[u];
	head[u]=idx;
}
void spfa(){
	memset(dis, 0x3f, sizeof(dis));
	dis[1]=0;
	queue<int>q;
	q.push(1);
	while(!q.empty()){
		int temp=q.front();
		book[temp]=false;
		q.pop();
		for(int i=head[temp];i!=0;i=e[i].nxt){
			if(dis[temp]+e[i].w<dis[e[i].to]){
				dis[e[i].to]=dis[temp]+e[i].w;
				pre[e[i].to]=temp;
				eid[e[i].to]=i;
				if(!book[e[i].to]){
					book[e[i].to]=true;
					q.push(e[i].to);
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		cin >> temp1 >> temp2 >> temp3;
		add_edge(temp1, temp2, temp3);
		add_edge(temp2, temp1, temp3);
	}
	spfa();
	ans1=dis[n];
	for(int walker=n;walker!=1;walker=pre[walker]){
		path[++pi]=eid[walker];
	}
	for(int i=1;i<=pi;i++){
		e[path[i]].w*=2;
		e[path[i]^1].w*=2;
		spfa();
		ans2=max(ans2, dis[n]);
		e[path[i]].w/=2;
		e[path[i]^1].w/=2;
	}
	cout << ans2 - ans1;
}