【题解】信使

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 1001
using namespace std;
int g[N][N]; 
int main(){
	int n,m,x,y,w;
	cin>>n>>m;
	memset(g,INF,sizeof(g));
	for(int i=1;i<=n;i++)
		g[i][i]=0;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>w;
		g[x][y]=g[y][x]=w;
	} 
	//floyd
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(g[i][j]>g[i][k]+g[k][j])
					g[i][j]=g[i][k]+g[k][j];
	int maxx=-INF;
	for(int i=1;i<=n;i++)
		if(g[1][i]>maxx)
			maxx=g[1][i];
	if(maxx==INF) cout<<"-1"<<endl;
	else cout<<maxx<<endl;
	return 0;
}