#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>; const int inf = 9e18; int32_t main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<Edge> edge(m); for (auto& [u, v, w] : edge) cin >> u >> v >> w, u--, v--; vector<int> P(m, 0); for (int i = m-2; i > -1; i--) P[i] = max(P[i+1], edge[i+1][2]); vector<int> S(n), T(n); vector<vector<pii>> G(n); for (auto [u, v, w] : edge) G[u].push_back({v, w}), G[v].push_back({u, w}); auto dijkstra = [&](int s, vector<int>& dist){ priority_queue<pii, vector<pii>, greater<pii>> pq; fill(entire(dist), inf); pq.push(pii{0, s}); while (!pq.empty()){ auto [W, u] = pq.top(); pq.pop(); if (dist[u] != inf) continue; else dist[u] = W; for (auto [v, w] : G[u]) pq.push(pii{W + w, v}); } }; dijkstra(0, S); dijkstra(n-1, T); auto check = [&](int lim){ bool good = false; vector<vector<Edge>> H(n); // H[u] -> { v, w, i } for (int i = 0; i < m; i++){ auto [u, v, w] = edge[i]; int dmin = min(S[u] + T[v], S[v] + T[u]) + w; if (dmin > lim) continue; good = true; H[u].push_back({v, w, i}); H[v].push_back({u, w, i}); } if (!good) return true; int timer = 0; vector<bool> vis(n, false); vector<int> tin(n), tout(n), ei(n), pi(n); vector<vector<int>> adj(n); auto dfs = [&](auto&& self, int s, int parent, int idx) -> void{ if (vis[s]) return; else vis[s] = true; ei[s] = idx, pi[s] = parent, tin[s] = timer++; for (auto [u, w, i] : H[s]) if (!vis[u]) { adj[s].push_back(u); self(self, u, s, i); } tout[s] = timer++; }; dfs(dfs, 0, 0, -1); vector<bool> bridge(m, false); vector<pii> dp(n, {inf, -1}); // minT, maxT auto dfsdp = [&](auto&& self, int s) -> bool{ bool npi = (s == n-1); for (auto u : adj[s]){ npi |= self(self, u); dp[s].ff = min(dp[u].ff, dp[s].ff); dp[s].ss = max(dp[u].ss, dp[s].ss); } for (auto [u, w, i] : H[s]) if (u != pi[s]){ dp[s].ff = min(dp[s].ff, tin[u]); dp[s].ss = max(dp[s].ss, tin[u]); } if (pi[s] == s) return npi; if (!(tin[s] <= dp[s].ff and dp[s].ss <= tout[s])) return npi; else if (npi) bridge[ei[s]] = true; return npi; }; dfsdp(dfsdp, 0); for (int i = 0; i < m; i++) if (bridge[i]){ auto [u, v, w] = edge[i]; int dist = min(S[u] + T[v], S[v] + T[u]) + w + P[i]; if (dist > lim) return true; } return false; }; int low = 0, high = 1e17; while (low < high){ int mid = (low + high + 1) / 2; if (check(mid)) low = mid; else high = mid-1; } cout << low + 1 << endl; return 0; }