#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define frep(i, l, r) for (int i = l; i >= r; i--)
#define eb emplace_back
#define pb push_back
#define endl "\n"
// #define int long long
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 1e6 + 3;
const int inf = 0x3f3f3f3f;
int n, m;
vector<PII> ve[N];
vector<int> dijkstra(int root)
{
    vector<int> d(n + 3, inf), vis(n + 3, 0);
    d[root] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> qu;
    qu.push({d[root], root});
    while (!qu.empty())
    {
        int t = qu.top().second;
        qu.pop();

        if (vis[t])
            continue;
        vis[t] = true;
        for (auto k : ve[t])
        {
            int u = k.first, v = k.second;
            if (d[v] > max(d[t], u))
            {
                d[v] = max(d[t], u);
                qu.push({d[v], v});
            }
        }
    }
    return d;
}
struct node
{
    int u, v, w;
} a[N];
void solve()
{
    cin >> n >> m;
    rep(i, 1, m)
    {
        int u, v, w;
        cin >> u >> v >> w;
        ve[u].pb({w, v});
        ve[v].pb({w, u});
        a[i] = node{u, v, w};
    }
    auto d1 = dijkstra(1), d2 = dijkstra(n);
    int res = 2e9;
    rep(i, 1, m)
    {
        int u = a[i].u, v = a[i].v, w = a[i].w;
        if (max(d1[u], d2[v]) <= w)
            res = min(res, w + max(d1[u], d2[v]));
    }
    cout << res << endl;
}
signed main()
{
    IOS;
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
}