#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300001;
const int M = 1000001;
int head[N];
int nxt[M << 1];
int to[M << 1];
int wei[M << 1];
int cnt = 1;
void ege(int a, int b, int c) {
    to[cnt] = b;
    wei[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt++;
}
int vis1[N], vis2[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> edge;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edge.push_back({a, b, c});
        ege(a, b, c);
        ege(b, a, c);
    }

    auto dijkstra = [&](int start, int *dist) {
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> que;
        fill(dist, dist + n + 1, LLONG_MAX);
        dist[start] = 0;
        que.push({0, start});
        
        while (!que.empty()) {
            auto [w, s] = que.top();
            que.pop();
            if (w > dist[s]) continue;
            for (int i = head[s]; i != 0; i = nxt[i]) {
                int nt = to[i];
                if (dist[s] + wei[i] < dist[nt]) {
                    dist[nt] = dist[s] + wei[i];
                    que.push({dist[nt], nt});
                }
            }
        }
    };

    // 运行双向 Dijkstra
    dijkstra(1, vis1);
    dijkstra(n, vis2);

    int ans = LLONG_MAX;
    for (auto [a, b, c] : edge) {
        int minPathThroughEdge = min(max(vis1[a], vis2[b]), max(vis1[b], vis2[a]));
        if (minPathThroughEdge <= c) {
            ans = min(ans, minPathThroughEdge + c);
        }
    }
    
    cout << ans << endl;
}