#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

typedef pair<int, int> P;

const int maxnode = , maxedge = , INF = ;

priority_queue<P, vector<P>, greater<P> > Q;

int n, m, fir[maxnode], nxt[maxedge], cnt, pre[maxnode], Ans;

int u[maxedge], v[maxedge], w[maxedge], dis[maxnode], bef;

bool cut[maxnode][maxnode], flag;

inline void addedge(int x, int y, int z) {

    nxt[++cnt] = fir[x];

    fir[x] = cnt;

    u[cnt] = x, v[cnt] = y, w[cnt] = z;

}

inline void Dijkstra() {

    Q.push(P(, ));

    fill(dis+, dis++n, INF);

    dis[] = ;

    P x;

    int k;

    while (!Q.empty()) {

        x = Q.top();

        Q.pop();

        if(x.first > dis[x.second]) continue;

        k = fir[x.second];

        while (k != -) {

            if(cut[u[k]][v[k]]) {

                if(dis[v[k]] > dis[u[k]] + w[k] + w[k]) {

                    dis[v[k]] = dis[u[k]] + w[k] + w[k];

                    Q.push(P(dis[v[k]], v[k]));

                }

            }

            else if(dis[v[k]] > dis[u[k]] + w[k]) {

                dis[v[k]] = dis[u[k]] + w[k];

                if(!flag) pre[v[k]] = u[k];

                Q.push(P(dis[v[k]], v[k]));

            }

            k = nxt[k];

        }

    }

}

int main() {

    scanf("%d%d", &n, &m);

    int x, y, z;

    memset(fir, -, sizeof(fir));

    for(int i=; i<=m; i++) {

        scanf("%d%d%d", &x, &y, &z);

        addedge(x, y, z);

        addedge(y, x, z);

    }

    flag = false;

    Dijkstra();

    flag = true;

    bef = dis[n];

    for(int i=n; i!=; i=pre[i]) {

        cut[i][pre[i]] = ;

        cut[pre[i]][i] = ;

        Dijkstra();

        cut[i][pre[i]] = ;

        cut[pre[i]][i] = ;

        Ans = max(Ans, dis[n]);

    }

    printf("%d", Ans-bef);

}