/**************************************************************

    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_pair

const 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;

}