#include<bits/stdc++.h>
#define For(i,m,n) for(register ll i=m;i<n;i++)
#define rFor(i,m,n) for(register ll i=m;i>n;i--)
#define r(a) read(a)
#define rr(a,b) read(a),read(b)
#define rrr(a,b,c) read(a),read(b),read(c)
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
template <class T>
inline void read(T &x)
{
    x=0;
    T f=1;
    char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    x=x*f;
}
const ll MaxN = 10001, MaxM = 100010;
const ll INF=9e18;
struct edge{
    ll next;
    ll to;
    ll dis;
    ll from;
    int ord;
}e[MaxM];
ll head[MaxN];
ll res[MaxN];
ll tot=0;
bool vis[MaxM];
ll n,m,s;
ll firstMinRoad=INF;
void add_edge(ll from,ll to,ll dis)
{
    tot++;
    e[tot].next=head[from];
    e[tot].to=to;
    e[tot].dis=dis;
    e[tot].from=from;
    e[tot].ord=tot;
    head[from]=tot;
}

struct node{
    ll dis;
    ll pos;
    vector<edge> path;
};
struct cmp{
    bool operator()(node &n1,node &n2)
    {
        if(n1.dis!=n2.dis)  return n1.dis>n2.dis;
        else                return n1.pos>n2.pos;
    }
};

priority_queue<node,vector<node>,cmp > Q;

vector<edge> dijkstra()
{
    For(i,1,n+1)   res[i]=INF;
    memset(vis,0,sizeof(vis));
    res[s]=0;
    vector<edge> tmp;
    Q.push((node){0,s,tmp});//保证从开始结点出发不断更新
    while(Q.size()){
        node now=Q.top();
        Q.pop();
        ll d=now.dis;
        ll x=now.pos;
        if(vis[x])    continue;
        vis[x]=1;
        for(ll i=head[x];i;i=e[i].next){
            node nxt=now;
            ll v=e[i].to;
            if(res[v]>res[x]+e[i].dis){
                res[v]=res[x]+e[i].dis;
                nxt.path.push_back(e[i]);
                if(v==n){
                    tmp=nxt.path;
                }
            }
            nxt.pos=v;
            nxt.dis=res[v];
            if(!vis[v]){
                Q.push(nxt);//保证了从起始节点往下走
            }
        }
    }
    return tmp;
}

int main()
{
    rr(n,m);s=1;

    For(i,1,m+1){
        ll u,v,d;
        rrr(u,v,d);
        add_edge(u,v,d);
        add_edge(v,u,d);
    }
    vector<edge> AllEdge=dijkstra();
    ll minnRoad=res[n];
    ll maxxRoad=-1;
    For(i,0,AllEdge.size()){
        edge now=AllEdge[i];
        e[now.ord].dis=e[now.ord].dis*2;
        dijkstra();
        e[now.ord].dis=e[now.ord].dis/2;
        maxxRoad=max(maxxRoad,res[n]);
    }
    cout<<maxxRoad-minnRoad;

    return 0;
}
//4 4
//1 2 2
//2 4 4
//1 3 2
//3 4 5