蒟蒻只会copy模板，没想到被Hack数据卡死，望各位巨佬，神犇提提思路。%%%%%%%%%

题目传送门：P1186 Code

#include<bits/stdc++.h>
#include<queue>
#include<vector>
using namespace std;
const int INF=0x7f7f7f7f;
typedef pair<int,int> PII;
int n,m,x,y,z,dp[1005],head[1005],pre[1005],tot,ans,dx,dy;
bool vis[1005],fir=true;
priority_queue <PII,vector<PII>,greater<PII> >Q;
struct edge{
	int next,to,cost;
}g[1000005];
void add(int u,int v,int w){
	g[++tot]=(edge){head[u],v,w};
	head[u]=tot;
}
void Dijkstra(){
	for(int i=1;i<=n;i++) dp[i]=INF,vis[i]=false;
	Q.push(make_pair(0,n));
	dp[n]=0;
	while(!Q.empty()){
		int u=Q.top().second;
		Q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];~i;i=g[i].next){
			int v=g[i].to;
			if(dx==v&&dy==u||dx==u&&dy==v) continue;
			if(dp[v]>dp[u]+g[i].cost){
				dp[v]=dp[u]+g[i].cost;
				if(fir) pre[v]=u;
				Q.push(make_pair(dp[v],v));
			}
		}
	}
	if(!fir) ans=max(ans,dp[1]);
}
int main(){
//	freopen("P1186_11.in","r",stdin);
//	freopen("P1186_my.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	Dijkstra();
	fir=false;
	for(int i=1;i;i=pre[i]){
		dx=i;
		dy=pre[i];
		Dijkstra();
	}
	printf("%d\n",ans);
	return 0;
}