#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int dis[N],pre[N];
struct PII{
  int first,second;
  bool operator<(const PII&b){
    return first<b.first;
  }
};
vector<PII>z[N];
set<PII>dd;
bool vis[N];
constexpr inline int max(int &a,int &b){return a>b?a:b;}
void spfaECVY(){
  queue<int>q;
  q.push(1);
  memset(dis,0x3f,sizeof dis);
  dis[1]=0;
  vis[1]=true;
  while(q.size()){ 
    register int f=q.front();q.pop();
    vis[f]=false;
    for(auto &[v,w]:z[f]){
      if(dis[v]>dis[f]+w){
        dis[v]=dis[f]+w;
        pre[v]=f;
        if(!vis[v]){
          vis[v]=true;
          q.push(v);
        }
      }
    }
  }
}
int mx=0,n,m;
void spfaSDJE(int ef,int fe){
  queue<int>q;
  q.push(1);
  memset(dis,0x3f,sizeof dis);
  dis[1]=0;
  vis[1]=true;
  while(q.size()){
    register int f=q.front();q.pop();
    vis[f]=false;
    for(auto &[v,w]:z[f]){
      if(f==ef&&v==fe||f==fe&&v==ef)continue;
      if(dis[v]>dis[f]+w){
        dis[v]=dis[f]+w;
        if(!vis[v]){
          vis[v]=true;
          q.push(v);
        }
      }
    }
  }
  mx=max(mx,dis[n]);
}
inline int read(){
  int x;char ch;
  while(!isdigit(ch=getchar()));
  x=ch^48;
  while(isdigit(ch=getchar()))x=(x<<3)+(x<<1)+(ch^48);
  return x;
}
signed main(){
  // freopen("a.in","r",stdin);
  n=read(),m=read();
  while(m--){
    register int a,b,c;
    a=read(),b=read(),c=read();
    z[a].push_back({b,c});
    z[b].push_back({a,c});
  }
  spfaECVY();
  for(register int i=n;i!=1;i=pre[i])
  {
    spfaSDJE(i,pre[i]);
    if(1.*clock()/CLOCKS_PER_SEC>=0.93)break;
  }
  cout<<mx<<'\n';
  // cout<<"Time Used: "<<1.*clock()/CLOCKS_PER_SEC<<'\n';
  return 0;
}

实测这一份暴力代码仍然可过。