#include <bits/stdc++.h> using namespace std; #define endl '\n' #define f first // #define s second #define pb(x) push_back(x) #define int long long const int MOD = 1e9+7; const int inf = 1e9; const int INF = 1e18+20; const int LOG = 25; struct edge { int a, b, w; }; int n, m; bool dfs (int u, int par, int &weight, vector<int> &path, vector<vector<pair<int, int>>> &adj) { if (u==n-1) { path.push_back(u); return true; } for (auto [v, w] : adj[u]) { if (v==par) continue; if (dfs(v, u, weight, path, adj)) { weight+=w; path.push_back(u); return true; } } return false; } void solve() { cin>>n>>m; vector<edge> edges(m); for (int i=0; i<m; i++) { int x, y, w; cin>>x>>y>>w; x--; y--; edges[i] = {x, y, w}; /*adj[x].push_back({y, w}); adj[y].push_back({x, w});*/ } auto key = [&](int x, int y) { if (x>y) swap(x, y); return (x<<32) | y; }; map<int, int> p; int mx = 0; for (int i=m-1; i>=0; i--) { int j = key(edges[i].a, edges[i].b); p[j] = mx; mx = max(mx, edges[i].w); } int ans=-1; for (int x=0; x<m; x++) { vector<vector<pair<int, int>>> adj(n); for (int i=0; i<m; i++) { int tt = edges[i].w; if (i==x) { int k = key(edges[i].a, edges[i].b); tt += (p[k]); } int u = edges[i].a; int v = edges[i].b; adj[u].push_back({v, tt}); adj[v].push_back({u, tt}); } vector<int> dist(n, INF); dist[0]=0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, 0}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (dist[u]!=d) continue; for (auto [v, w] : adj[u]) { if (dist[v] > d+w) { dist[v]=d+w; pq.push({dist[v],v}); } } } ans=max(ans, dist[n-1]); } cout<<ans<<endl; /*int weight=0; vector<int> path; dfs(0, -1, weight, path, adj); int tt=-1; for (int i=1; i<path.size(); i++) { int j = key(path[i], path[i-1]); tt= max(tt, p[j]); } weight+=tt; cout<<weight<<endl;*/ } bool multi=false; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t=1; if (multi) cin>>t; while (t--) solve(); return 0; }