#include #include #include #include #include #include using namespace std; struct DSU { vector p, s; explicit DSU(int n) : p(n), s(n, 1) { iota(p.begin(), p.end(), 0); } int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (s[a] < s[b]) swap(a, b); p[b] = a; s[a] += s[b]; return true; } }; struct Edge { int u, v; long long w; bool tree = false; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector edges(m); vector order(m); for (int i = 0; i < m; ++i) { cin >> edges[i].u >> edges[i].v >> edges[i].w; --edges[i].u; --edges[i].v; order[i] = i; } sort(order.begin(), order.end(), [&](int a, int b) { return edges[a].w < edges[b].w; }); vector>> tree(n); DSU dsu(n); long long total = 0; for (int id : order) if (dsu.unite(edges[id].u, edges[id].v)) { edges[id].tree = true; total += edges[id].w; tree[edges[id].u].push_back({edges[id].v, edges[id].w}); tree[edges[id].v].push_back({edges[id].u, edges[id].w}); } constexpr int log = 20; vector> up(log, vector(n)); vector> maximum(log, vector(n)); vector depth(n, -1); queue q; depth[0] = 0; up[0][0] = 0; q.push(0); while (!q.empty()) { int u = q.front(); q.pop(); for (auto [v, w] : tree[u]) if (depth[v] == -1) { depth[v] = depth[u] + 1; up[0][v] = u; maximum[0][v] = w; q.push(v); } } for (int j = 1; j < log; ++j) for (int v = 0; v < n; ++v) { up[j][v] = up[j - 1][up[j - 1][v]]; maximum[j][v] = max(maximum[j - 1][v], maximum[j - 1][up[j - 1][v]]); } auto path_max = [&](int u, int v) { long long answer = 0; if (depth[u] < depth[v]) swap(u, v); for (int j = log - 1; j >= 0; --j) if (depth[u] - (1 << j) >= depth[v]) { answer = max(answer, maximum[j][u]); u = up[j][u]; } if (u == v) return answer; for (int j = log - 1; j >= 0; --j) if (up[j][u] != up[j][v]) { answer = max({answer, maximum[j][u], maximum[j][v]}); u = up[j][u]; v = up[j][v]; } return max({answer, maximum[0][u], maximum[0][v]}); }; for (const Edge &e : edges) { cout << (e.tree ? total : total + e.w - path_max(e.u, e.v)) << '\n'; } }