#include<iostream>
#include<cstring>
using namespace std;
int to[5005],nxt[5005],head[105],a[5005],dis[105],vis[105],n,m;
int dijkstra(){
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    for(int i=1;i<=n;i++){
        int minn=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&(minn==-1||dis[j]<dis[minn])){
                minn=j;
            }
        }
        //cout<<minn<<"\n";
        vis[minn]=1;
        for(int j=head[minn];j;j=nxt[j]){
            int v=to[j];
            if(dis[minn]+a[j]<dis[v]){
                dis[v]=dis[minn]+a[j];
            }
        }
    }
    cout<<dis[n]<<"\n";
    return dis[n];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        nxt[i]=head[u];
        to[i]=v;
        head[u]=i;
        a[i]=w;
    }
    int now=dijkstra(),maxn=0;
    for(int i=1;i<=m;i++){
        a[i]*=2;
        maxn=max(maxn,dijkstra()-now);
        a[i]/=2;
    }
    cout<<maxn;
    return 0;
}