#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int inf = 2000000000 + 10;

struct D {
    int u, dis, d1, d2;

    D() {}
    D(int u, int dis, int d1, int d2) : u(u), dis(dis), d1(d1), d2(d2) {}

    bool operator < (const D &x) const {
        return (dis < x.dis || (dis == x.dis && d1 < x.d1));
    }
    bool operator > (const D &x) const {
        return (dis > x.dis || (dis == x.dis && d1 > x.d1));
    }
};

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> e(n);
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        u--;
        v--;
        e[u].emplace_back(v, c);
        e[v].emplace_back(u, c);
    }

    priority_queue<D, vector<D>, greater<D>> pq;
    pq.emplace(0, 0, 0, 0);

    vector<int> dis(n, inf);

    while (!pq.empty()) {
        auto [u, d, d1, d2] = pq.top();
        pq.pop();

        if (d >= dis[u]) {
            continue;
        }
        // cerr << "u: " << u + 1 << ", d: " << d << ", d1: " << d1 << ", d2: " << d2 << endl;

        dis[u] = d;
        for (auto [v, c] : e[u]) {
            int nd1 = d1, nd2 = d2;
            if (c > nd2) {
                nd2 = c;
            }
            if (nd2 > nd1) {
                swap(nd1, nd2);
            }

            pq.emplace(v, nd1 + nd2, nd1, nd2);
        }
    }

    // for (int i = 0; i < n; i++) {
    //     cerr << "u: " << i + 1 << ", dis: " << dis[i] << endl;
    // }

    cout << dis.back() << endl;

    return 0;
}