思路：先跑一遍迪杰斯特拉，搜原来的最短路，复杂度O(n^2)，再枚举每条边都倍长的情况，找最长，复杂度(mn^2)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[5010],maxx=-1e9,now,b[5010],c[5010],d[210];
bool f[210];
vector<pair<int,int>>e[210];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>a[i]>>b[i]>>c[i];
	for(int j=1;j<=n;j++)e[j].clear(),d[j]=1e9;
	for(int j=1;j<=m;j++)
	e[a[j]].push_back(make_pair(b[j],c[j]));
	d[1]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int p=q.top().second;
		q.pop();
		if(f[p])continue;
		f[p]=true;
		for(auto k:e[p]){
			int x=k.first;
			int y=k.second;
			if(d[x]>d[p]+y){
				d[x]=d[p]+y;
				q.push(make_pair(d[x],x));
			}
		}
	}
	now=d[n];
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)e[j].clear(),d[j]=1e9,f[j]=false;
		for(int j=1;j<=m;j++){
			if(j!=i)e[a[j]].push_back(make_pair(b[j],c[j]));
			else e[a[j]].push_back(make_pair(b[j],c[j]*2));
		}
		d[1]=0;
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
		q.push(make_pair(0,1));
		while(!q.empty()){
			int p=q.top().second;
			q.pop();
			if(f[p])continue;
			f[p]=true;
			for(auto k:e[p]){
				int x=k.first;
				int y=k.second;
				if(d[x]>d[p]+y){
					d[x]=d[p]+y;
					q.push(make_pair(d[x],x));
				}
			}
		}
		maxx=max(maxx,d[n]);
	}
	cout<<maxx-now<<endl;
    return 0;
}