/**************************************************************    Problem: 3445    User: BeiYu    Language: C++    Result: Accepted    Time:32 ms    Memory:3332 kb****************************************************************/ #include <cstdio>#include <cstring>#include <utility>#include <vector>#include <queue>#include <functional>#include <iostream>using namespace std; typedef long long LL;typedef pair< LL,int > pr;#define mpr make_pairconst int N = 255; int n,m,cnt;int b[N],p[N];LL ans,disn;LL d[N];struct Edge{ int fr,to;LL w; }edge[N*N*2];vector< int > g[N];priority_queue< pr,vector< pr >,greater< pr > > q;vector< int > path; inline int in(int x=0){ scanf("%d",&x);return x; }void Add_Edge(int fr,int to,int w){    edge[++cnt]=(Edge){ fr,to,w };    g[fr].push_back(cnt);}void GetPath(){    for(int x=n;x!=1;x=edge[p[x]].fr) path.push_back(p[x]);}void Dijstra(int s,int fst){    memset(b,0,sizeof(b));    memset(d,0x3f,sizeof(d));    d[s]=0,q.push(mpr(0LL,s));    for(int x;!q.empty();){        x=q.top().second,q.pop();if(b[x]) continue;b[x]=1;        for(int i=0,lim=g[x].size();i<lim;i++){            int v=edge[g[x][i]].to;LL w=edge[g[x][i]].w;//          cout<<x<<" "<<v<<" "<<w<<" "<<d[x]<<" "<<d[v]<<endl;            if(d[x]+w < d[v]){                d[v]=d[x]+w,p[v]=g[x][i];                q.push(mpr(d[v],v));            }        }    }//  cout<<d[n]<<endl;    if(fst) disn=d[n],GetPath();    else ans=max(ans,d[n]-disn);}int main(){    n=in(),m=in();    for(int i=1,u,v,w;i<=m;i++) u=in(),v=in(),w=in(),Add_Edge(u,v,w),Add_Edge(v,u,w);    Dijstra(1,1);     //  for(int i=0,lim=path.size();i<lim;i++) cout<<edge[path[i]].fr<<" "<<edge[path[i]].to<<" "<<edge[path[i]].w<<endl;         for(int i=0,lim=path.size();i<lim;i++) edge[path[i]].w*=2,Dijstra(1,0),edge[path[i]].w/=2;    cout<<ans<<endl;    return 0;}