#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + 5;
vector<pair<int, int>>e[maxn];
bool vis[maxn], vis1[maxn];
int dis[maxn];
int mx[maxn];
pii d[maxn];
struct node1 {
    int id, mx;
    friend bool operator <(node1 a, node1 b) {
        return a.mx > b.mx;
    }
};
void bfs() {
    priority_queue<node1>q;
    mx[1] = 0;
    q.push({ 1,0 });
    while (!q.empty()) {
        auto [u, _] = q.top();
        q.pop();
        if (vis1[u])continue;
        vis1[u] = true;
        for (auto [v, w] : e[u]) {
            if (mx[v] > max(mx[u], w)) {
                mx[v] = max(mx[u], w);
                q.push({ v,mx[v] });
            }
        }
    }
}
struct node {
    int id;
    int x, y;
    friend bool operator <(node a, node b) {
        return a.x + a.y > b.x + b.y;
    }
};
void dij() {
    priority_queue<node>q;
    dis[1] = 0;
    q.push({ 1,0,0 });
    while (!q.empty()) {
        auto [u, x, y] = q.top();
        q.pop();
        if (vis[u])continue;
        vis[u] = true;
        for (auto [v, w] : e[u]) {
            if (w >= y) {
                if (dis[v] > w + mx[u]) {
                    dis[v] = w + mx[u];
                    d[v] = { max(w,mx[u]),min(w,mx[u]) };
                    q.push({ v, max(w, mx[u]), min(w, mx[u]) });
                } else if (dis[v] == w + mx[u] && d[v].se > min(w, mx[u])) {
                    d[v] = { max(w,mx[u]),min(w,mx[u]) };
                    q.push({ v, max(w, mx[u]), min(w, mx[u]) });
                }
            } else {
                if (dis[v] > dis[u]) {
                    dis[v] = dis[u];
                    d[v] = { x,y };
                    q.push({ v,x,y });
                } else if (dis[v] == dis[u] && d[v].se > y) {
                    d[v] = { x,y };
                    q.push({ v, x, y });
                }
            }
        }
    }
}
void solve() {
    int n, m;
    cin >> n >> m;
    int res = 2e9 + 7;
    memset(dis, 0x3f, sizeof dis);
    memset(mx, 0x3f, sizeof mx);
    for (int i = 1;i <= m;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({ v,w });
        e[v].push_back({ u,w });
    }
    bfs();
    dij();
    cout << dis[n] << endl;
}
signed main() {
    int t = 1;
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while (t--) {
        solve();
    }
}