During the Kruskal algorithm, at any point, the maximum-weighted edge between any $$$u$$$ and $$$v$$$ (obviously belonging to the same component) is the weight of the edge that merged their two components.

Consider the MST for the graph. Now, for each edge $$$e = {u, v, w}$$$, add it to the MST. Now the MST has only one cycle, containing the path between $$$u$$$ and $$$v$$$ plus edge $$$e$$$. Since the structure of the MST except the cycle is still intact, we only have to remove one edge from the cycle to restore the tree structure. Since the question asks for the minimum sum of weights (while containing edge $$$e$$$), we can remove the maximum-weighted edge from the cycle, not including edge $$$e$$$, to get the MST containing edge $$$e$$$.

If we implement this naively (like my original sol using DFS, 389622797) we will have an $$$O(m\logm + mn)$$$ solution, which will unfortunately TLE, as discussed before. :(

But we can use the property discussed above to reach an acceptable solution:

For each edge $$$e = {u, v, w}$$$ we can pre-calculate the maximum-weighted edge between $$$u$$$ and $$$v$$$'s path, with weight $$$mxw$$$. Then the answer for $$$e$$$ becomes:

And for the pre-calculation we use the property described above + StoL vector-based DSU — when merging two trees in the Kruskal algorithm, we set $$$mxw$$$ for all the edges between the two components to $$$w$$$.

For a better understanding of the pre-calc itself, view the implementation, and for a better understanding of its complexity, view the source linked for StoL DSU.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define fi  first
#define se  second
#define pb  push_back

#define Fast    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define Tests   int tt; cin >> tt; while(tt--) input(), solve(), output();
#define Single  input(), solve(), output();

// ----------------------------------------------------- //
//   █████╗  ██████╗  ██╗   ██╗  █████╗  ███╗   ██╗      //
//  ██╔══██╗ ██╔══██╗ ╚██╗ ██╔╝ ██╔══██╗ ████╗  ██║      //
//  ███████║ ██████╔╝  ╚████╔╝  ███████║ ██╔██╗ ██║ :):  //
//  ██╔══██║ ██╔══██╗   ╚██╔╝   ██╔══██║ ██║╚██╗██║      //
//  ██║  ██║ ██║  ██║    ██║    ██║  ██║ ██║ ╚████║      //
//  ╚═╝  ╚═╝ ╚═╝  ╚═╝    ╚═╝    ╚═╝  ╚═╝ ╚═╝  ╚═══╝      //
// ----------------------------------------------------- //
// 0 1 2 3 4 5 6 7 8 9 | n = 10

const int N = 2e5 + 5, M = 2e5 + 5;
struct edge {int u, v, w, idx;} ed[M];
vector<pair<int, int>> adj[N];
int n, m, id[N], mxw[M];
set<int> cmp[N];
ll mstw;

void move(int v, int u, int w) { // move v to u
    // handle edges between components
    for (int x : cmp[v])
        for (auto [y, idx] : adj[x])
            if (cmp[u].count(y))
                mxw[idx] = w;

    // move nodes from component v to u
    for (int x : cmp[v]) {
        id[x] = u;
        cmp[u].insert(x);
    }
    cmp[v].clear();
}

bool merge(edge x) {
    int u = id[x.u];
    int v = id[x.v];

    if (u == v)
        return false;

    cmp[u].size() < cmp[v].size() ? move(u, v, x.w) : move(v, u, x.w);
    return true;
}

void input() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;

        ed[i] = {u, v, w, i};
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }
}

void solve() {
    for (int u = 0; u < n; u++) {
        cmp[u].insert(u);
        id[u] = u;
    }

    sort(ed, ed + m, [](const edge a, const edge b ) {
        return a.w < b.w;
    });

    for (int i = 0; i < m; i++)
        mstw += (ll)ed[i].w * merge(ed[i]);
}



void output() {
    sort(ed, ed + m, [](const edge a, const edge b ) {
        return a.idx < b.idx;
    });

    for (int i = 0; i < m; i++)
        cout << mstw - mxw[i] + ed[i].w << '\n';
}

int main() {
    Fast
    // Tests
    Single
}