#include<bits/stdc++.h>
using namespace std;
int vis1[1005],vis2[1003],n,m,s,t;
int ans;
struct edge{int v,w;};
int dis1[1005],dis2[1005];
vector<edge>vt1[10005],vt2[10086];
struct node{
	int point,dist;
	bool operator > (const node& a) const{return dist>a.dist;}
};
priority_queue<node,vector<node>,greater<node> > q;
int main(){
	int u,v,w;
	cin>>n>>m;
	memset(dis1,0x3f,sizeof(dis1));memset(dis2,0x3f,sizeof(dis2));
	while(m--){
		cin>>u>>v>>w;
		vt1[u].push_back({v,w});
		vt2[v].push_back({u,w});
	}
	dis1[1]=0;
	q.push({1,0});
	while(!q.empty()){
		u = q.top().point;q.pop();
		if(vis1[u])continue;
		vis1[u]=1;
		for(int i=0;i<vt1[u].size();i++){
			 v = vt1[u][i].v , w = vt1[u][i].w;
			 if(dis1[v] > dis1[u]+w){
			 	dis1[v] = dis1[u]+w;
			 	q.push({v,dis1[v]});
			 }	
		}
	}//fan xiang
	dis2[1]=0;
	q.push({1,0});
	while(!q.empty()){
		u = q.top().point;q.pop();
		if(vis2[u])continue;
		vis2[u]=1;
		for(int i=0;i<vt2[u].size();i++){
			 v = vt2[u][i].v , w = vt2[u][i].w;
			 if(dis2[v] > dis2[u]+w){
			 	dis2[v] = dis2[u]+w;
			 	q.push({v,dis2[v]});
			 }	
		}
	}ans=-1;
	for(int i=1;i<=n;i++){
		ans=max(ans,dis1[i]+dis2[i]);
	}
	
	cout<<ans;
	return 0;
}

关注*1