p01671 Minimum Spanning Tree_17050
E - Minimum Spanning Tree

Problem Statement

You are given an undirected weighted graph G with n nodes and m edges. Each edge is numbered from 1 to m.

Let G_i be an graph that is made by erasing i-th edge from G. Your task is to compute the cost of minimum spanning tree in G_i for each i.

Input

The dataset is formatted as follows.


n m
a_1 b_1 w_1
...
a_m b_m w_m


The first line of the input contains two integers n (2 \leq n \leq 100{,}000) and m (1 \leq m \leq 200{,}000). n is the number of nodes and m is the number of edges in the graph. Then m lines follow, each of which contains a_i (1 \leq a_i \leq n), b_i (1 \leq b_i \leq n) and w_i (0 \leq w_i \leq 1{,}000{,}000). This means that there is an edge between node a_i and node b_i and its cost is w_i. It is guaranteed that the given graph is simple: That is, for any pair of nodes, there is at most one edge that connects them, and a_i \neq b_i for all i.

Output

Print the cost of minimum spanning tree in G_i for each i, in m line. If there is no spanning trees in G_i, print "-1" (quotes for clarity) instead.

Sample Input 1


4 6
1 2 2
1 3 6
1 4 3
2 3 1
2 4 4
3 4 5


Output for the Sample Input 1


8
6
7
10
6
6


Sample Input 2


4 4
1 2 1
1 3 10
2 3 100
3 4 1000


Output for the Sample Input 2


1110
1101
1011
-1


Sample Input 3


7 10
1 2 1
1 3 2
2 3 3
2 4 4
2 5 5
3 6 6
3 7 7
4 5 8
5 6 9
6 7 10


Output for the Sample Input 3


27
26
25
29
28
28
28
25
25
25


Sample Input 4


3 1
1 3 999


Output for the Sample Input 4


-1






Example

Input

4 6
1 2 2
1 3 6
1 4 3
2 3 1
2 4 4
3 4 5


Output

8
6
7
10
6
6
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005 , maxm = 400005;
const long long inf = 41351356514454ll;
typedef pair<int , long long> pii;
#define x first
#define y second
struct edge{
	int u , v , p;
	long long w;
	edge(){}
	void read(int i){scanf("%d%d%lld" , &u , &v , &w);p=i;}
	friend bool operator < (const edge &a , const edge &b){return a.w < b.w;}
}e[25][maxm] , t[maxm] , d[maxm];
pii q[maxm];
int n , m , qc;
long long sum[maxn] , f[maxn] , sz[maxn] , c[maxm] , a[maxm];
long long ans[maxm];
void reset(edge *s , int tot)
{
	for (int i = 1 ; i <= tot ; i++)
		f[s[i].u] = s[i].u , f[s[i].v] = s[i].v;
}
int set_find(int u){return f[u] == u ? u : f[u] = set_find(f[u]);}
void set_merge(int u , int v){f[set_find(u)] = set_find(v);}
void cont(int &tot , long long &cnt)
{
	int tmp = 0;
	reset(d , tot);
	sort(&d[1] , &d[tot + 1]);
	for (int i = 1 ; i <= tot ; i++)
		if (set_find(d[i].u) != set_find(d[i].v))
			set_merge(d[i].u , d[i].v) , t[++tmp] = d[i];
	reset(t , tmp);
	for (int i = 1 ; i <= tmp ; i++)
		if (t[i].w != -inf && set_find(t[i].u) != set_find(t[i].v))
			set_merge(t[i].u , t[i].v) , cnt+=t[i].w;
	tmp = 0;
	for (int i = 1 ; i <= tot ; i++)
		if (set_find(d[i].u) != set_find(d[i].v))
			t[c[d[i].p] = ++tmp] = d[i],
				t[tmp].u = f[d[i].u],
				t[tmp].v = f[d[i].v];
	for (int i = 1 ; i <= tmp ; i++)
		d[i] = t[i];
	tot = tmp;
}
void redu(int &tot)
{
	int tmp = 0;
	reset(d , tot);
	sort(&d[1] , &d[tot + 1]);
	for (int i = 1 ; i <= tot ; i++)
		if (set_find(d[i].u) != set_find(d[i].v))
			set_merge(d[i].u , d[i].v),
				t[c[d[i].p] = ++tmp] = d[i];
		else if (d[i].w == inf)
			t[c[d[i].p] = ++tmp] = d[i];
	for (int i = 1 ; i <= tmp ; i++) d[i] = t[i];
	tot = tmp;
}
void solv(int l , int r , int lay , long long cnt)
{
	int tot = sum[lay];
	if (l == r) a[q[l].x] = q[l].y;
	for (int i = 1 ; i <= tot ; i++) e[lay][i].w = a[e[lay][i].p];
	for (int i = 1 ; i <= tot ; i++) d[i] = e[lay][i] , c[d[i].p] = i;
	if (l == r)
	{
		ans[l] = cnt;
		reset(d , tot);
		sort(&d[1] , &d[tot + 1]);
		for (int i = 1 ; i <= tot ; i++)
			if (set_find(d[i].u) != set_find(d[i].v))
				set_merge(d[i].u , d[i].v) , ans[l] += d[i].w;
		return;
	}
	for (int i = l ; i <= r ; i++) d[c[q[i].x]].w = -inf;
	cont(tot , cnt);
	for (int i = l ; i <= r ; i++) d[c[q[i].x]].w = inf;
	redu(tot);
	for (int i = 1 ; i <= tot ; i++) e[lay + 1][i] = d[i];
	sum[lay + 1] = tot;
	int mid = (l + r) / 2;
	solv(l , mid , lay + 1 , cnt);
	solv(mid + 1 , r , lay + 1 , cnt);
}
int main()
{
	scanf("%d%d" , &n , &m);
	for (int i = 1 ; i <= m ; i++)
	{
		e[0][i].read(i);a[i] = e[0][i].w;
		q[++qc] = pii(i , (long long)1e13);
		q[++qc] = pii(i , e[0][i].w);
	}
	sum[0] = m;
	solv(1 , qc , 0 , 0);
	for (int i = 1 ; i <= qc ; i += 2)
		printf("%lld\n" , ans[i] < 1e13 ? ans[i] : -1ll);
	return 0;
}