#include <bits/stdc++.h> using namespace std; #define endl "\n" #define int long long #define pii pair<int, int> #define ff first #define ss second #define entire(x) (x).begin(), (x).end() using Edge = array<int, 3>; int32_t main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<Edge>> adj(n); vector<Edge> edge(m); for (int i = 0; i < m; i++){ int u, v, w; cin >> u >> v >> w; u--, v--; edge[i] = Edge{u, v, w}; if (u == v) continue; adj[u].push_back({v, w, i}); adj[v].push_back({u, w, i}); } vector<int> suff(m+1, 0); for (int i = m-1; i > -1; i--) suff[i] = max(suff[i+1], edge[i][2]); vector<bool> vis(n, false); pii ans; auto dfs = [&](auto&& self, int s, int pi, int W, int idx) -> void{ if (vis[s]) return; else vis[s] = true; if (s == n-1) ans = {W, idx}; for (auto [u, w, i] : adj[s]) if (u != pi) self(self, u, s, W + w, min(idx, i)); }; dfs(dfs, 0, 0, 0, m-1); cout << ans.ff + suff[ans.ss + 1] << endl; return 0; }