//
// Created by wind on 24-10-13.
//

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int inf = 1e18;

#define vv vector
#define int long long
#define p11 pair<long long, long long>
#define per(a, b, c) for(int a = b; a <= c; a ++)
#define pb emplace_back

struct E
{
    int u, v, w;
};


void solve() {
    int n, m;
    cin >> n >> m;
    vv<vv<p11>> e(n + 1);
    vv<E> edge(m + 1);
    per(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].pb(v, w);
        e[v].pb(u, w);
        edge[i] = {u, v, w};
    }
    vv<int> mx1(n + 1, inf), mx2(n + 1, inf);
    vv<int> d1(n + 1, inf), d2(n + 1, inf);
    vv<int> vis1(n + 1), vis2(n + 1);
    d1[1] = 0;
    priority_queue<array<int, 2>, vv<array<int, 2>>, greater<array<int, 2>>> q1;
    q1.push({0, 1});
    while(q1.size())
    {
        auto [_, u] = q1.top();
        q1.pop();
        if(vis1[u]) continue;
        vis1[u] = 1;
        for(auto [v, w] : e[u])
        {
            if(d1[v] > d1[u] + w)
            {
                d1[v] = d1[u] + w;
                q1.push({d1[v], v});
            }
        }
    }
    per(i, 1, n) vis1[i] = 0;
    mx1[1] = 0;
    priority_queue<array<int, 2>, vv<array<int, 2>>, greater<array<int, 2>>> qq1;
    qq1.push({0, 1});
    while(qq1.size())
    {
        auto [nw, u] = qq1.top();
        qq1.pop();
        if(vis1[u]) continue;
        vis1[u] = 1;
        for(auto [v, w] : e[u])
        {
            int nw = max(w, mx1[u]);
            if(mx1[v] > nw)
            {
                mx1[v] = nw;
                qq1.push({nw, v});
            }
        }
    }
    d2[n] = 0;
    priority_queue<array<int, 2>, vv<array<int, 2>>, greater<array<int, 2>>> q2;
    q2.push({0, n});
    while(q2.size())
    {
        auto [_, u] = q2.top();
        q2.pop();
        if(vis2[u]) continue;
        vis2[u] = 1;
        for(auto [v, w] : e[u])
        {
            if(d2[v] > d2[u] + w)
            {
                d2[v] = d2[u] + w;
                q2.push({d2[v], v});
            }
        }
    }
    per(i, 1, n) vis2[i] = 0;
    mx2[n] = 0;
    priority_queue<array<int, 2>, vv<array<int, 2>>, greater<array<int, 2>>> qq2;
    qq2.push({0, n});
    while(qq2.size())
    {
        auto [nw, u] = qq2.top();
        qq2.pop();
        if(vis2[u]) continue;
        vis2[u] = 1;
        for(auto [v, w] : e[u])
        {
            int nw = max(w, mx2[u]);
            if(mx2[v] > nw)
            {
                mx2[v] = nw;
                qq2.push({nw, v});
            }
        }
    }
    int ans = inf;
    per(i, 1, m)
    {
        auto [u, v, w] = edge[i];
        auto check = [&](int x, int y)
        {
            int w1 = d1[x], w2 = d2[y];
            if(w1 > w || w2 > w) return;
            ans = min(ans, max(w1, w2) + w);
        };
        check(u, v);
        check(v, u);
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

/*
4 6
1 2 2
1 3 4
1 4 7
2 3 1
2 4 3
3 4 9

4 4
1 2 99
2 4 99
1 3 1
3 4 100



 */