#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300001;
const int M = 1000001;
int head[N], nexxt[M << 1], to[M << 1], wei[M << 1];
int cnt = 1;

void ege(int a, int b, int c) {
    to[cnt] = b;
    wei[cnt] = c;
    nexxt[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);
    }

    // 初始化距离为无限大，起点和终点初始化为0
    fill(vis1, vis1 + n + 1, LLONG_MAX);
    fill(vis2, vis2 + n + 1, LLONG_MAX);
    vis1[1] = 0;
    vis2[n] = 0;

    // 从起点1开始计算最大边权路径
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> que;
    que.push({0, 1});
    while (!que.empty()) {
        auto [we, s] = que.top();
        que.pop();
        if (we > vis1[s]) continue;
        for (int i = head[s]; i != 0; i = nexxt[i]) {
            int nt = to[i];
            int w = max(we, wei[i]);
            if (w < vis1[nt]) {
                vis1[nt] = w;
                que.push({vis1[nt], nt});
            }
        }
    }

    // 从终点n开始计算最大边权路径
    que.push({0, n});
    while (!que.empty()) {
        auto [we, s] = que.top();
        que.pop();
        if (we > vis2[s]) continue;
        for (int i = head[s]; i != 0; i = nexxt[i]) {
            int nt = to[i];
            int w = max(we, wei[i]);
            if (w < vis2[nt]) {
                vis2[nt] = w;
                que.push({vis2[nt], nt});
            }
        }
    }

    // 寻找最小路径
    int ans = LLONG_MAX;
    for (auto [a, b, c] : edge) {
        int direct_path_cost = c;  // 直接连接的路径
        int indirect_path_cost = c + min(max(vis1[a], vis2[b]), max(vis1[b], vis2[a]));

        // 选取较小的路径
        ans = min(ans, indirect_path_cost);
    }

    cout << ans << endl;
}