E. Minimum spanning tree for each edge

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli maxN = 2e5;
const lli maxM = 2e5;
const lli logN = log2(maxN);
using pll = pair <lli, lli>;
struct Graph{
    lli i, w, u, v;
};
Graph graph[maxM + 10];
bool is_mst[maxM + 10];
lli n, m;

/// sort
bool compare_w(Graph a, Graph b){
    if(a.w == b.w) return a.i < b.i;
    return a.w < b.w;
}
bool compare_i(Graph a, Graph b){
    return a.i < b.i;
}

/// MST
lli mst_par[maxN + 10];
vector <pll> mst_graph[maxN + 10];
lli root(lli u){
    if(mst_par[u] == u) return u;
    return mst_par[u] = root(mst_par[u]);
}

void mrg(lli u, lli v){
    u = root(u);
    v = root(v);
    mst_par[v] = u;
}

/// LCA
lli lca_par[maxN + 10][logN + 10], lca_max[maxN + 10][logN + 10];
lli level[maxN + 10];
void dfs(lli u, lli p, lli lvl, lli pw){
    level[u] = lvl;
    lca_par[u][0] = p;
    lca_max[u][0] = pw;
    for(auto g: mst_graph[u]){
        lli v = g.first;
        lli w = g.second;
        if(v == p) continue;
        dfs(v, u, lvl + 1, w);
    }
}

/// max edge to ancestor
lli MaxEdge(lli u, lli v, lli mx = 0){ /// u -> v
    if(level[u] < level[v]) swap(u, v);
    for(lli e=logN;e>=0;e--){ /// [2 ^ logN, 2^0]
        if(level[ lca_par[u][e] ] >= level[v]){
            mx = max(mx, lca_max[u][e]);
            u = lca_par[u][e];
        }
    }
    if(u == v) return mx;
    for(lli e=logN;e>=0;e--){ /// [2 ^ logN, 2^0]
        if(lca_par[u][e] != lca_par[v][e]){
            mx = max({mx, lca_max[u][e], lca_max[v][e]});
            u = lca_par[u][e];
            v = lca_par[v][e];
        }
    }
    mx = max({mx, lca_max[u][0], lca_max[v][0]});
    return mx;
}

int main(){

    scanf("%lld %lld", &n, &m);

    for(lli i=1;i<=m;i++){
        lli u, v, w;
        scanf("%lld %lld %lld", &u, &v, &w);
        if(u > v) swap(u, v);
        graph[i] = {i, w, u, v};
    }

    /// MST
    for(lli i=1;i<=n;i++) mst_par[i] = i;
    sort(graph + 1, graph + m + 1, compare_w);
    lli mst_sum = 0;
    for(lli i=1;i<=m;i++){
        if(root(graph[i].u) == root(graph[i].v)) continue;
        mst_sum += graph[i].w;
        mrg(graph[i].u, graph[i].v);
        mst_graph[ graph[i].u ].push_back({graph[i].v, graph[i].w});
        mst_graph[ graph[i].v ].push_back({graph[i].u, graph[i].w});
        is_mst[ graph[i].i ] = true;
    }

    /// LCA
    dfs(1, 0, 1, 0);
    for(lli e=1;e<=logN;e++){
        for(lli u=1;u<=n;u++){
            lca_par[u][e] = lca_par[ lca_par[u][e - 1] ][e - 1];
            lca_max[u][e] = max(lca_max[u][e - 1], lca_max[ lca_par[u][e - 1] ][e - 1]);
        }
    }

    /// query
    sort(graph + 1, graph + m + 1, compare_i);
    for(lli i=1;i<=m;i++){
        if(is_mst[i]) printf("%lld\n", mst_sum);
        else{
            lli w = graph[i].w;
            lli u = graph[i].u;
            lli v = graph[i].v;
            lli mxe = MaxEdge(u, v);
            printf("%lld\n", mst_sum - mxe + w);
        }
    }

    return 0;
}