Sleigh Ride

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using Edge = pair<int, ll>;
    5vector<vector<Edge>> g;
    6ll farDist;
    7void dfs(int u, int p, ll acc){
    8    farDist = max(farDist, acc);
    9    for(auto [v, w] : g[u]){
    10        if(v == p) continue;
    11        dfs(v, u, acc + w);
    12    }
    13}
    14int main(){
    15    ios::sync_with_stdio(0);
    16    cin.tie(0);
    17    int m; cin >> m;
    18    vector<tuple<int,int,ll>> edges;
    19    edges.reserve(m);
    20    int maxv = 0;
    21    ll sumW = 0;
    22    for(int i = 0; i < m; i++){
    23        int u, v; ll w;
    24        cin >> u >> v >> w;
    25        edges.emplace_back(u, v, w);
    26        maxv = max(maxv, max(u, v));
    27        sumW += w;
    28    }
    29    int n = maxv + 1;
    30    g.assign(n, {});
    31    for(auto [u, v, w] : edges){
    32        g[u].push_back({v, w});
    33        g[v].push_back({u, w});
    34    }
    35    // Only need farthest distance from 0
    36    farDist = 0;
    37    dfs(0, -1, 0);
    38    ll ans = 2LL * sumW - farDist;
    39    cout << ans << "\n";
    40    return 0;
    41}
    42