609E - MST For Each Edge

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <ctime>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>

#define ll long long
#define II pair<int, int>
#define III pair<int, pair<int, int>>
#define DI pair<double, int>
#define fs first
#define sc second
#define mp(a, b) make_pair(a, b)

const ll LINF = 9223372036854775807;
const int INF = 2147483647;
const int MAX_N = 200005;

using namespace std;

int bit(int x, int k) {
    return (1ll & (x >> k));
}

struct Edge {
    int u, v, w, id;
    Edge(int u, int v, int w, int id) : u(u), v(v), w(w), id(id) {};
};

struct Data {
    int par;
    ll maxc = -LINF;
};

struct DSU {

    vector<int> par;

    void init(int n) {
        par.resize(n+5, 0);
        for(int i = 0; i <= n; i++) par[i] = -1;
    }

    int find(int u) {
        return (par[u] < 0 ? u : par[u] = find(par[u]));
    }

    bool join(int u, int v) {
        u = find(u); v = find(v);
        if(u == v) return false;
        par[v] = u;
        return true;
    }

} dsu;

int n, m, q, h[MAX_N];
ll weight = 0;
ll ans[MAX_N];
Data up[MAX_N][22];
vector<Edge> edges;
vector<II> g[MAX_N];


void dfs(int u, int p) {
    up[u][0].par = p;

    for(auto& e : g[u]) {
        int v = e.fs, c = e.sc;

        if(v == p) continue;
        h[v] = h[u] + 1;
        up[v][0].maxc = c;
        dfs(v, u);
    }
}

void buildLCA() {
    dfs(1, 1);
    for (int i = 1; i <= 20; i++) {
        for (int u = 1; u <= n; u++) {
            up[u][i].par = up[up[u][i - 1].par][i - 1].par;
            up[u][i].maxc = max(up[u][i - 1].maxc, up[up[u][i - 1].par][i - 1].maxc);
        }
    }
}

ll solve(int u, int v) {

    ll ret;
    if (h[u] < h[v]) swap(u, v);
    int dep = h[u] - h[v];

    for (int i = 20; i >= 0; i--) {
        if (bit(dep, i)) {
            ret = max(ret, up[u][i].maxc);
            u = up[u][i].par;
        }
    }

    if (u == v) return ret;

    for (int i = 20; i >= 0; --i) {
        if (up[u][i].par != up[v][i].par) {
            ret = max({ret, up[u][i].maxc, up[v][i].maxc});
            u = up[u][i].par; v = up[v][i].par;
        }
    }

    return max({ret, up[u][0].maxc, up[v][0].maxc});
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    freopen("E.INP", "r", stdin);
    freopen("E.OUT", "w", stdout);

    cin >> n >> m;

    int u, v, c;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> c;
        edges.push_back({u, v, c, i});
    }

    dsu.init(n);

    sort(edges.begin(), edges.end(), [](Edge& a, Edge& b) {
        return a.w < b.w;
    });

    int cnt = 0;
    for(auto& e : edges) {
        if(!dsu.join(e.u, e.v)) continue;
        cnt ++;
        weight += e.w;
        ans[e.id] = -1;
        g[e.u].push_back({e.v, e.w});
        g[e.v].push_back({e.u, e.w});
        if(cnt == n) break;
    }

    buildLCA();

    for(auto& e : edges) {
        if(ans[e.id] == -1) ans[e.id] = weight;
        else ans[e.id] = weight - solve(e.u, e.v) + e.w;
    }

    for(int i = 1; i <= m; i++) cout << ans[i] << endl;
    return 0;
}