1 #include <cstdio>  2 #include <iostream>  3 #include <algorithm>  4 #include <utility>  5 #include <map>  6 #include <string>  7 #include <cmath>  8 #include <vector>  9 #include <cstring> 10 #include <stack> 11 #include <set> 12 #include <queue> 13  14 using namespace std; 15  16 #define SQR(x) ((x)*(x)) 17 #define LL long long 18 #define LOWBIT(x) ((x)&(-(x))) 19 #define PB push_back 20 #define MP make_pair 21 #define SQR(x) ((x)*(x)) 22 #define LSON(x) ((x)<<1) 23 #define RSON(x) (((x)<<1)+1) 24  25  26  27 #define MAXN 211111 28  29 const double EPS = 1e-6; 30  31 LL ans, spanTree; 32 int n, m; 33  34 struct line{ 35     int a, b, c, id; 36     line(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), id(d) {} 37     bool operator < (const line &rhs) const { 38         return c < rhs.c; 39     } 40 }; 41  42 line a[MAXN]; 43 int w[MAXN]; 44  45 struct DisjointSet{ 46     int f[MAXN], n; 47     void init(int nn = MAXN - 10) { 48         n = nn; 49         for (int i = 0; i <= n; ++i) { 50             f[i] = i; 51         } 52     } 53     int get(int x) { 54         return f[x] == x ? x : f[x] = get(f[x]); 55     } 56     void joint(int x, int y) { 57         f[x] = y; 58     } 59 } DjS; 60  61 struct data{ 62     int dest, cost; 63     data *nxt; 64     data(int a = 0, int b = 0, data *c = 0): dest(a), cost(b), nxt(c) {} 65 }; 66  67 struct TreeArray{ 68     int tree[MAXN], n; 69     int a[MAXN]; 70     void init(int nn = MAXN - 1) { 71         n = nn; 72         memset(tree, 0, sizeof(tree[0])*(n+10)); 73     } 74     void add(int x, int num = -1) { 75         a[x] = num; 76         while (x <= n) { 77             tree[x] = max(tree[x], num); 78             x += LOWBIT(x); 79         } 80     } 81     int get(int x, int y) { 82         int res = -1; 83         while (x <= y) { 84             if (y - LOWBIT(y) >= x) { 85                 res = max(res, tree[y]); 86                 y -= LOWBIT(y); 87             } else { 88                 res = max(res, a[y]); 89                 --y; 90             } 91         } 92         return res; 93     } 94 } TA; 95  96 struct Tree{ 97     data edge[MAXN*2], *vect[MAXN]; 98     int n, cnt; 99     int sz[MAXN], top[MAXN], heavy[MAXN], father[MAXN], dep[MAXN], lab[MAXN], num;100     int root;101     //???0?4??0?3??0?3??102     void add(int x, int y, int z) {103         edge[++cnt] = data(y, z, vect[x]); vect[x] = &edge[cnt];104     }105 106     void init(int nn = MAXN - 10, int roott = 1) {107         n = nn;108         cnt = num = 0; 109         memset(vect, 0, sizeof(vect[0])*(n+10));110         memset(father, -1, sizeof(father[0])*(n+10));111         root = roott;112     }113 114     void split_dfs1(int u = 1) {115         sz[u] = 1; heavy[u] = -1;116         for (data *i = vect[u]; i; i = i->nxt) {117             if (i->dest == father[u]) continue;118             father[i->dest] = u;119             dep[i->dest] = dep[u] + 1;120             w[i->dest] = i->cost;121             split_dfs1(i->dest);122             sz[u] += sz[i->dest];123             if (heavy[u] == -1 || sz[i->dest] > sz[heavy[u]]) heavy[u] = i->dest;124         }125     }126 127     void split_dfs2(int u = 1, int anc = 1) {128         top[u] = anc; lab[u] = ++num;129         TA.add(lab[u], w[u]);130         if (heavy[u] != -1) split_dfs2(heavy[u], anc);131         for (data *i = vect[u]; i; i = i->nxt) {132             if (i->dest != father[u] && i->dest != heavy[u]) split_dfs2(i->dest, i->dest);133         }134     }135 136     void split() {137         w[root] = -1;138         dep[root] = 1;139         father[root] = -1;140         141         split_dfs1(root);142 143         num = 0;144 145         split_dfs2(root, root);146     }147 148     int query(int u, int v) {149         int res = -1;150         //cout << "query ================  " << ‘ ‘<< endl;151         //cout << u << ‘ ‘<< v << endl;152         //cout << top[u] <<‘ ‘<< top[v] << endl;153         while (top[u] != top[v]) {154             if (dep[top[u]] < dep[top[v]]) swap(u, v);155             //todo156         //    cout << u << ‘ ‘<< v << ‘ ‘<< top[u] << ‘ ‘<< top[v] << endl;157             res = max(res, TA.get(lab[top[u]], lab[u]));158         //    cout << res << endl;159             //todo end160             u = father[top[u]];161         }162         if (dep[u] > dep[v]) swap(u, v);163         164         //cout << u << ‘ ‘<< v << endl;165         //cout << lab[u] << ‘ ‘ << lab[v] << endl;166         //todo167         res = max(res, TA.get(lab[u]+1, lab[v]));168         //todo end169         return res;170     }171 } G;172 173 void init() {174     cin >> n >> m;175     DjS.init(n);176     G.init(n);177     TA.init(n);178 179     int x, y, z;180     for (int i = 0; i < m; ++i) {181         cin >> x >> y >> z;182         a[i] = line(x, y, z, i);183     }184     sort(a, a + m);185     int cnt = 0;186     spanTree = 0;187     188     for (int i = 0 ; i < m; ++i) {189         int x = a[i].a, y = a[i].b;190         x = DjS.get(x); y = DjS.get(y);191         if (x != y) {192             //cout << "=============" << endl;193             //cout << a[i].a << ‘ ‘ << a[i].b << ‘ ‘<< a[i].c << endl;194             DjS.joint(x, y);195             spanTree += a[i].c;196             ++cnt;197             G.add(a[i].a, a[i].b, a[i].c);198             G.add(a[i].b, a[i].a, a[i].c);199             a[i].c *= -1;200         }201         if (cnt + 1 == n) break;202     }203     204     G.split();205     206 }207 208 bool cmp2(const line &a, const line &b) {209     return a.id < b.id;210 }211 212 void solve() {213     214     //cout << spanTree << endl;215     sort(a, a + m, cmp2);216     ans = 0;217     for (int i = 0; i < m; ++i) {218         if (a[i].c < 0) {219             ans = spanTree;220         }221         else {222             ans = spanTree - G.query(a[i].a, a[i].b) + a[i].c;223             //cout << a[i].a << ‘ ‘ << a[i].b << endl;224             //cout << G.query(a[i].a, a[i].b) << ‘ ‘<< a[i].c << endl;225         }226         cout << ans << endl;227     }228 }229 230 int main() {231     //freopen("test.txt", "r", stdin);232     ios::sync_with_stdio(false);233     init();234     solve();235     return 0;236 }