MST Include edge[i] - MST + LCA (609E - Codeforces)

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 2e5;
const long long oo = 1e18;
bool InTree[N + 1];
long long d[N + 1], M[N + 1][21], mst = 0;
int n, m, parent[N + 1][21], logg[N + 1], depth[N + 1];
struct TEdge
{
    int u, v;
    long long w;
};
TEdge e[N + 1];
using PEdge = TEdge *;
PEdge p[N + 1];
vector<int> Adj[N + 1];
struct TPQItem
{
    int node;
    long long dlab;
    bool operator < (const TPQItem & other) const
    {
        return other.dlab < dlab;
    }
    bool Valid()
    {
        return d[node] == dlab;
    }
};
priority_queue<TPQItem> PQ;
void read()
{
   cin >> n >> m;
   for (int i = 1; i <= m; ++ i)
   {
       cin >> e[i].u >> e[i].v >> e[i].w;
       p[i] = &e[i];
       Adj[e[i].v].push_back(i);
       Adj[e[i].u].push_back(i);
   }
   logg[1] = 0;
   for (int i = 2; i <= N; ++ i)
   {
       logg[i] = logg[i/2] + 1;
   }
}
void Prim()
{
    fill(InTree + 1, InTree + n + 1, false);
    fill(d + 1, d + n + 1, oo);
    d[1] = 0;
    parent[1][0] = 1;
    PQ.push({1, 0LL});
    while (!PQ.empty())
    {
        TPQItem r = PQ.top();
        PQ.pop();
        if (!r.Valid())
        {
            continue;
        }
        int u = r.node;
        for (int k = 1; k <= logg[n]; ++ k)
        {
            parent[u][k] = parent[parent[u][k-1]][k-1];
            M[u][k] = max(M[u][k-1], M[parent[u][k-1]][k - 1]);
        }
        InTree[u] = true;
        mst += d[u];
        for (int i : Adj[u])
        {
            int v = p[i]->u ^ p[i]->v ^ u;
            if (!InTree[v] && d[v] > p[i]->w)
            {
                d[v] = p[i]->w;
                PQ.push({v, d[v]});
                parent[v][0] = u;
                M[v][0] = d[v];
                depth[v] = depth[u] + 1;
            }
        }
    }
}
long long MaxLCAEdge(int u, int v)
{
    long long ans = 0;
    if (depth[u] < depth[v])
    {
        swap(u, v);
    }
    int k = depth[u] - depth[v];
    for (int i = 0; i < logg[n]; ++ i)
    {
        if (k & (1 << i))
        {
            ans = max(ans, M[u][i]);
            u = parent[u][i];
        }
    }
    if (u == v)
    {
        return ans;
    }
    for (int i = logg[n] - 1; i >= 0; -- i)
    {
        if (parent[u][i] != parent[v][i])
        {
            ans = max({ans, M[u][i], M[v][i]});
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return max({ans, M[u][0], M[v][0]});
}
void solve()
{
   Prim();
   for (int i = 1; i <= m; ++ i)
   {
       cout << mst - MaxLCAEdge(p[i]->u, p[i]->v) + p[i]->w << '\n';
   }
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   //freopen(TASK".INP", "r", stdin);
   //freopen(TASK".OUT", "w", stdout);
   int t = 1;
   bool typetest = false;
   if (typetest)
   {
      cin >> t;
   }
   for (int __ = 1; __ <= t; ++ __)
   {
      cerr << "Case " << __ << ":" << '\n';
      read();
      solve();
   }
}