#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const int N = 2e6 + 5;
const ll P = 1e9 + 7;
ll m, n, q, tot;
vector<pii> ve[N];
struct node {
    ll x, y, w;
} st[N];
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> st[i].x >> st[i].y >> st[i].w;
        ve[st[i].x].push_back({st[i].y, st[i].w});
        ve[st[i].y].push_back({st[i].x, st[i].w});
    }
    vector<ll> dis1(n + 2);
    vector<ll> dis2(n + 2);
    auto dij = [&](int now) -> void {
        vector<int> v(n + 2);
        vector<ll> dis(n + 2, 1e12);
        dis[now] = 0;
        priority_queue<pii, vector<pii>, greater<pii>> q;
        q.push({0, now});
        while (q.size()) {
            auto [d, x] = q.top();
            q.pop();
            if (v[x]) {
                continue;
            }
            v[x] = 1;
            for (auto [y, w] : ve[x]) {
                if (dis[y] > max(d, w)) {
                    dis[y] = min(dis[y], max(d, w));
                    q.push({dis[y], y});
                }
            }
        }
        if (now == 1) {
            for (int i = 1; i <= n; i++) {
                dis1[i] = dis[i];
            }
        } else {
            for (int i = 1; i <= n; i++) {
                dis2[i] = dis[i];
            }
        }
    };
    dij(1);
    dij(n);
    ll ans = 1e12;
    for (int i = 1; i <= m; i++) {
        auto [x, y, w] = st[i];
        // cout << dis1[x] << ' ' << dis2[y] << '\n';
        ll sum = w + dis1[x] + dis2[y];
        if(x==1||x==n||y==1||y==n){continue;}
        ans = min(ans, sum - min({w, dis1[x], dis2[y]}));
        sum = w + dis1[y] + dis2[x];
        ans = min(ans, sum - min({w, dis1[y], dis2[x]}));
    }
    cout << ans;
}

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