#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); vector<vector<pair<int, int>>> adj(n); 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 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; } /* graph is a tree, find the path between 1 to n, find least aesthetic road in that path, then for every road more aethetic than this road find the max w[j]. add that to our shortest path answer. */ 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; }