#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e6 + 10, INF = 1e9 + 7;

struct edge {
    int u, v, w;
} e[N];
int d[N][2], n, m, f[N];

vector<int>g[N];
int find(int x)
{
    if (f[x] != x)f[x] = find(f[x]);
    return f[x];
}

bool cmp(edge x, edge y) {
    return x.w < y.w;
}

void merge(int u, int v, int x, int w)
{
    if (find(u) == find(x) && find(v) == find(x))return;
    if (find(u) != find(x) && find(v) != find(x))return;
    if (find(u) != find(x))swap(u, v);
    for (auto y : g[find(v)]) {
        if (x == 1)d[y][0] = min(d[y][0], w);
        else d[y][1] = min(d[y][1], w);
    }
}


void solve()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e, e + m, cmp);
    for (int i = 1; i <= n; i++)
    {
        f[i] = i, g[i].push_back(i);
        for (int j = 0; j < 2; j++)d[i][j] = INF;
    }
    int res = 2 * INF;
    d[1][0] = 0, d[n][1] = 0;
    for (int i = 0; i < m; i++) {
        auto [u, v, w] = e[i];
        for (int j = 0; j < 2; j++)res = min(res, w + max(d[u][j] , d[v][j ^ 1]));
        merge(u, v, 1, w), merge(u, v, n, w);
        u = find(u), v = find(v);
        if (u == v)continue;
        if (g[u].size() < g[v].size())swap(u, v);
        for (auto y : g[v])g[u].push_back(y);
        f[v] = u;
    }
    cout << res;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}