#include <bits/stdc++.h>
using namespace std;
// using ll = long long;
#define int long long

int n, m;
int i, j, k;
vector<pair<int, int> > v[300010];
int dis1[300010], dis2[300010];//1:1-x; 2:n-x
int vis[300010];
struct Node {
    int u, dis;
    Node(int u, int dis) : u(u), dis(dis) {}
    bool operator < (const Node& rhs) const {
        return dis > rhs.dis;
    }
};

void dij1(int s) {
    Node nn = Node(s, 0);
    priority_queue<Node> pq;
    pq.push(nn);
    while(!pq.empty()) {
        Node t = pq.top();
        pq.pop();
        int u = t.u, dis = t.dis;
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto p : v[u]) {
            int v = p.first, w = p.second;
            if(dis1[v] > max(dis1[u], w)) {
                dis1[v] = max(dis1[u], w);
                pq.push(Node(v, dis1[v]));
            }
        }
    }
}

void dij2(int s) {
    Node nn = Node(s, 0);
    priority_queue<Node> pq;
    pq.push(nn);
    while(!pq.empty()) {
        Node t = pq.top();
        pq.pop();
        int u = t.u, dis = t.dis;
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto p : v[u]) {
            int v = p.first, w = p.second;
            if(dis2[v] > max(dis2[u], w)) {
                dis2[v] = max(dis2[u], w);
                pq.push(Node(v, dis2[v]));
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for(i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    memset(dis1, 0x3f, sizeof(dis1));
    memset(dis2, 0x3f, sizeof(dis2));
    memset(vis, 0, sizeof(vis));
    dis1[1] = 0;
    dis2[n] = 0;
    dij1(1);
    memset(vis, 0, sizeof(vis));
    dij2(n);
    // for (i = 1; i <= n; i ++)
    // {
    //     cout << dis1[i] << " " << dis2[i] << "\n";
    // }
    int ans = 0x3f3f3f3f;
    for (i = 1; i <= n; i ++)
    {
        for (j = 0; j < v[i].size(); j ++)
        {
            int x = v[i][j].first, y = v[i][j].second;
            int ans1 = dis1[i] + dis2[x] + y - min(y, min(dis1[i], dis2[x]));
            int ans2 = dis1[x] + dis2[i] + y - min(y, min(dis1[x], dis2[i]));
            // cout << i << " " << x << " " << y << " " << ans1 << " " << ans2 << "\n";
            ans = min(ans, min(ans1, ans2));
        }
    }
    cout << ans << "\n";
}

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