// implement 70min #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; static const double EPS = 1e-9; static const double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define MEMSET(v, h) memset((v), h, sizeof(v)) struct UnionFind { int parent[100010]; UnionFind() { memset(parent, -1, sizeof(parent)); } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x == y) { return false; } if (parent[y] < parent[x]) { swap(x, y); } parent[x] += parent[y]; parent[y] = x; return true; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); } }; typedef ll Weight; struct Edge { int src; int dest; Weight weight; int index; Edge(int src, int dest, Weight weight, int index) : src(src), dest(dest), weight(weight), index(index) {;} bool operator<(const Edge &rhs) const { if (weight != rhs.weight) { return weight < rhs.weight; } if (src != rhs.src) { return src < rhs.src; } return dest < rhs.dest; } }; typedef set Edges; typedef vector Graph; int n, m; Graph g; Graph tree; Edges es; UnionFind ufind; int order[200010]; int eindex[200010]; int parent[200010]; ll pweight[200010]; ll ans[200010]; Edges groups[200010]; void CalcTree() { FORIT(it, es) { if (ufind.unionSet(it->src, it->dest)) { tree[it->src].insert(Edge(it->src, it->dest, it->weight, it->index)); tree[it->dest].insert(Edge(it->dest, it->src, it->weight, it->index)); } } } ll CalcOrderAndSum() { ll sum = 0; int index = 0; queue que; que.push(Edge(0, 0, 0, -1)); while (!que.empty()) { Edge e = que.front(); que.pop(); int p = e.src; int from = e.dest; sum += e.weight; order[index] = from; eindex[from] = e.index; parent[from] = p; pweight[from] = e.weight; index++; FORIT(it, tree[from]) { int to = it->dest; if (to == p) { continue; } que.push(Edge(from, to, it->weight, it->index)); } } reverse(order, order + n); return sum; } void Merge(int p, int c) { if (groups[p].size() < groups[c].size()) { swap(groups[p], groups[c]); } FORIT(it, groups[c]) { groups[p].insert(*it); } ufind.unionSet(p, c); } void CalcTreeAnswer(ll sum) { ufind = UnionFind(); REP(i, n - 1) { int index = order[i]; FORIT(it, g[index]) { if (ufind.findSet(it->src, it->dest) || it->dest == parent[index]) { continue; } groups[index].insert(*it); } ll lans = -1; while ((int)groups[index].size() > 0) { Edge e = *groups[index].begin(); if (ufind.findSet(e.src, e.dest)) { groups[index].erase(groups[index].begin()); continue; } lans = sum + e.weight - pweight[index]; break; } ans[eindex[index]] = lans; Merge(parent[index], index); } } int main() { while (scanf("%d %d", &n, &m) > 0) { // Init g = Graph(n); tree = Graph(n); es.clear(); ufind = UnionFind(); MEMSET(order, -1); MEMSET(eindex, -1); MEMSET(parent, -1); MEMSET(pweight, -1); REP(i, 200010) { groups[i].clear(); } // Input REP(i, m) { int f, t, w; int v = scanf("%d %d %d", &f, &t, &w); f--; t--; assert(v == 3); es.insert(Edge(f, t, w, i)); g[f].insert(Edge(f, t, w, i)); g[t].insert(Edge(t, f, w, i)); } CalcTree(); if (-ufind.parent[ufind.root(0)] != n) { REP(i, m) { puts("-1"); } continue; } ll sum = CalcOrderAndSum(); REP(i, m) { ans[i] = sum; } CalcTreeAnswer(sum); REP(i, m) { printf("%lld\n", ans[i]); } } }