99pts求条，必关

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int maxn=1000+20,inf=1234567890;
typedef pair<int,int> P;
struct edge{int to,w;};
vector<edge>G[maxn];
int n,m,pre[maxn],d[maxn];
priority_queue<P,vector<P>,greater<P> >que;
void read(int &n){
    n=0;int f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    do{
        n=n*10+ch-'0';
        ch=getchar();
    }while(ch>='0' && ch<='9');
    n=n*f;
    return;
}
void write(int n){
    if(n<0){
        putchar('-');
        n=0-n;
    }
    if(n>=10) write(n/10);
    putchar((n % 10)+'0');
    return;
}
inline void add_edge(int u,int v,int w){
    edge e;e.to=v;e.w=w;
    G[u].push_back(e);
    return;
}
void init(){
    read(n);read(m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        read(u);read(v);read(w);
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    return;
}
int dijkstra(int f,int ff){
    for(int i=1;i<=n;i++) d[i]=inf;
    d[1]=0;
    P p(0,1);que.push(p);
    while(!que.empty()){
        P temp=que.top();
        que.pop();
        int u=temp.second;
        if(d[u]<temp.first) continue;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].to;
            if(f==u && ff==v) continue;
            if(ff==u && f==v) continue;
            int w=G[u][i].w;
            int t=d[u]+w;
            if(d[v]>t){
                d[v]=t;
                que.push(P(t,v));
                if(!f && !ff) pre[v]=u;
            }
        }
    }
    return d[n];
}
void solve(){
    memset(pre,-1,sizeof(pre));
    int ans=dijkstra(0,0);
    int u=n;
    while(pre[u]!=-1){
        int r=dijkstra(u,pre[u]);
        if(r!=inf) ans=max(ans,r);
        u=pre[u];
    }
    write(ans);
    return;
}
int main(){
    init();
    solve();
    return 0;
}