#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define ff first
#define ss second
#define INFF 9223372036854775807
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
using namespace std;
using PII = pair<int, int>;
using ULL = unsigned long long;
using ld = long double;
const int N = 4e5 + 10;
const int M = 2e6 + 10;
int n,m;
int ds[N],dt[N]; // ds是从起点到点i的最大权值边是多少
bool vs[N],vt[N];
int h[M],e[M],ne[M],idx,w[M];
int ans = 1e18;
struct Node
{
    int x,y,z;
}arr[N];

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++;
}

void dijkstra1(int S)
{
    for(int i = 1;i <= n;i ++)
    {
        ds[i] = INFF;
        vs[i] = 0;
    }
    ds[S] = 0;
    priority_queue<PII,vector<PII>,greater<>> pq;
    pq.emplace(0,S);
    while(!pq.empty())
    {
        auto [dis,u] = pq.top();
        pq.pop();
        if(vs[u]) continue;
        vs[u] = true;
        for(int i = h[u];~i;i = ne[i])
        {
            int v = e[i];
            if(ds[v] > max(w[i],dis))
            {
                ds[v] = max(w[i],dis);
                pq.emplace(max(w[i],dis),v);
            }
        }
    }
}

void dijkstra2(int S)
{
    for(int i = 1;i <= n;i ++)
    {
        dt[i] = INFF;
        vt[i] = 0;
    }
    dt[S] = 0;
    priority_queue<PII,vector<PII>,greater<>> pq;
    pq.emplace(0,S);
    while(!pq.empty())
    {
        auto [dis,u] = pq.top();
        pq.pop();
        if(vt[u]) continue;
        vt[u] = true;
        for(int i = h[u];~i;i = ne[i])
        {
            int v = e[i];
            if(dt[v] > max(w[i],dis))
            {
                dt[v] = max(w[i],dis);
                pq.emplace(max(w[i],dis),v);
            }
        }
    }
}

void solve()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i = 1;i <= m;i ++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
        Node t = {a,b,c};
        arr[i] = t;
        if((a == 1 && b == n) || (a == n && b == 1)) ans = min(ans,c);
    }
    dijkstra1(1);
    dijkstra2(n);

    // for(int i = 1;i <= n;i ++)
    // {
    //     deg(ds[i]);
    //     den(dt[i]);
    // }
    
    for(int i = 1;i <= m;i ++)
    {
        int mx = arr[i].z;
        int x = arr[i].x,y = arr[i].y;
        int temp = min(max(ds[x],dt[y]),max(ds[y],dt[x]));
        if(mx < temp) continue;
        ans = min(ans,mx + temp);
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}