#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

struct unifo{
	int n;
	int uni[200005];
	void init(int in){
		n=in;
		rep(i,n)uni[i]=i;
	}
	int find(int p){
		if(uni[p]==p)return p;
		else return (uni[p]=find(uni[p]));
	}
	void mer(int p,int q){
		if(!same(p,q))uni[find(p)]=find(q);
	}
	bool same(int p,int q){
		return find(p)==find(q);
	}
	void out(){
		vector<mp> ps;
		//printf("%d %d\n",i,find(i));
		rep(i,n)ps.push_back(mp(find(i),i));
		sort(ps.begin(),ps.end());
		printf("uni .. %d elem\n{ ",n);
		rep(i,n){
			if(i!=0 && ps[i-1].fir!=ps[i].fir)printf("}\n{ ");
			printf("%d ",ps[i].sec);
		}
		printf("}\n\n");
	}
} uni;

typedef pair<int,mp> mmp;
typedef pair<lli,int> lip;

int n,m;
vector<mp> bvs[100005];

vector<lli> ecs;
vector<mp> eds;
vector<int> ess;
mp vs[100005];

lli sc=0;
lli ans[200005]={};

int dep[100005];

void cdfs(int no,int p,int d){
	dep[no]=d;
	rep(i,bvs[no].size()){
		mp pa = bvs[no][i];
		int to=pa.fir,e=pa.sec;
		if(to==p)continue;
		vs[to]=mp(no,e);
		cdfs(to,no,d+1);
	}
}

int dub[100005][20];

void lcainit(){
	rep(i,n)dub[i][0]=vs[i].fir;
	rep(k,19){
		rep(i,n){
			dub[i][k+1] = dub[dub[i][k]][k];
		}
	}
}

int getlca(int p,int q){
	if(dep[p]<dep[q])swap(p,q);
	irep(i,20){
		if(dep[p]-dep[q]>=(1<<i)){
			p = dub[p][i];
		}
	}
	
	irep(i,20){
		if(dub[p][i]==dub[q][i])continue;
		p = dub[p][i];
		q = dub[q][i];
	}
	
	if(p!=q){
		p = dub[p][0];
		q = dub[q][0];
	}
	return p;
}

void focus(int fr,int to,lli dco){
	for(;;){
		if(uni.same(fr,to))break;
		fr = uni.find(fr);
		mp pa = vs[fr];
		int tf = pa.fir,
			e  = pa.sec;
		ans[e]=sc+dco-ecs[e];
		uni.mer(fr,tf);
		fr = tf;
	}
}


int main(void){
	scanf("%d%d",&n,&m);
	rep(i,m){
		int a,b; lli c;
		scanf("%d%d%lld",&a,&b,&c); a--; b--;
		ecs.push_back(c);
		eds.push_back(mp(a,b));
	}
	
	{
		vector<lip> v;
		rep(i,m)v.push_back(lip(ecs[i],i));
		sort(v.begin(),v.end());
		rep(i,m)ess.push_back(v[i].sec);
	}
	
	{
		uni.init(n+5);	
		vector<int> v;
		int spn=0;
		rep(i,m){
			int e = ess[i];
			int a = eds[e].fir,
				b = eds[e].sec;
			if(uni.same(a,b)){
				ans[e]=-2;
				v.push_back(e);
				continue;
			}
			ans[e]=-1; spn++;
			bvs[a].push_back(mp(b,e));
			bvs[b].push_back(mp(a,e));
			sc += ecs[e];
			uni.mer(a,b);
		}
		if(spn!=n-1){
			rep(i,m)printf("-1\n");
			return 0;
		}
		swap(v,ess);
		rep(i,m){
			if(ans[i]==-2)ans[i]=sc;
		}
	}
	
	cdfs(0,-1,0);
	lcainit();
	uni.init(n+5);	
	
	rep(i,ess.size()){
		int e = ess[i];
		int a = eds[e].fir,
			b = eds[e].sec;
		if(uni.same(a,b))continue;
		
		int anc = getlca(a,b);
		focus(a,anc,ecs[e]);
		focus(b,anc,ecs[e]);
	}
	
	rep(i,m)printf("%lld\n",ans[i]);
	
	return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

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

### Response

```cpp
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

struct unifo{
	int n;
	int uni[200005];
	void init(int in){
		n=in;
		rep(i,n)uni[i]=i;
	}
	int find(int p){
		if(uni[p]==p)return p;
		else return (uni[p]=find(uni[p]));
	}
	void mer(int p,int q){
		if(!same(p,q))uni[find(p)]=find(q);
	}
	bool same(int p,int q){
		return find(p)==find(q);
	}
	void out(){
		vector<mp> ps;
		//printf("%d %d\n",i,find(i));
		rep(i,n)ps.push_back(mp(find(i),i));
		sort(ps.begin(),ps.end());
		printf("uni .. %d elem\n{ ",n);
		rep(i,n){
			if(i!=0 && ps[i-1].fir!=ps[i].fir)printf("}\n{ ");
			printf("%d ",ps[i].sec);
		}
		printf("}\n\n");
	}
} uni;

typedef pair<int,mp> mmp;
typedef pair<lli,int> lip;

int n,m;
vector<mp> bvs[100005];

vector<lli> ecs;
vector<mp> eds;
vector<int> ess;
mp vs[100005];

lli sc=0;
lli ans[200005]={};

int dep[100005];

void cdfs(int no,int p,int d){
	dep[no]=d;
	rep(i,bvs[no].size()){
		mp pa = bvs[no][i];
		int to=pa.fir,e=pa.sec;
		if(to==p)continue;
		vs[to]=mp(no,e);
		cdfs(to,no,d+1);
	}
}

int dub[100005][20];

void lcainit(){
	rep(i,n)dub[i][0]=vs[i].fir;
	rep(k,19){
		rep(i,n){
			dub[i][k+1] = dub[dub[i][k]][k];
		}
	}
}

int getlca(int p,int q){
	if(dep[p]<dep[q])swap(p,q);
	irep(i,20){
		if(dep[p]-dep[q]>=(1<<i)){
			p = dub[p][i];
		}
	}
	
	irep(i,20){
		if(dub[p][i]==dub[q][i])continue;
		p = dub[p][i];
		q = dub[q][i];
	}
	
	if(p!=q){
		p = dub[p][0];
		q = dub[q][0];
	}
	return p;
}

void focus(int fr,int to,lli dco){
	for(;;){
		if(uni.same(fr,to))break;
		fr = uni.find(fr);
		mp pa = vs[fr];
		int tf = pa.fir,
			e  = pa.sec;
		ans[e]=sc+dco-ecs[e];
		uni.mer(fr,tf);
		fr = tf;
	}
}


int main(void){
	scanf("%d%d",&n,&m);
	rep(i,m){
		int a,b; lli c;
		scanf("%d%d%lld",&a,&b,&c); a--; b--;
		ecs.push_back(c);
		eds.push_back(mp(a,b));
	}
	
	{
		vector<lip> v;
		rep(i,m)v.push_back(lip(ecs[i],i));
		sort(v.begin(),v.end());
		rep(i,m)ess.push_back(v[i].sec);
	}
	
	{
		uni.init(n+5);	
		vector<int> v;
		int spn=0;
		rep(i,m){
			int e = ess[i];
			int a = eds[e].fir,
				b = eds[e].sec;
			if(uni.same(a,b)){
				ans[e]=-2;
				v.push_back(e);
				continue;
			}
			ans[e]=-1; spn++;
			bvs[a].push_back(mp(b,e));
			bvs[b].push_back(mp(a,e));
			sc += ecs[e];
			uni.mer(a,b);
		}
		if(spn!=n-1){
			rep(i,m)printf("-1\n");
			return 0;
		}
		swap(v,ess);
		rep(i,m){
			if(ans[i]==-2)ans[i]=sc;
		}
	}
	
	cdfs(0,-1,0);
	lcainit();
	uni.init(n+5);	
	
	rep(i,ess.size()){
		int e = ess[i];
		int a = eds[e].fir,
			b = eds[e].sec;
		if(uni.same(a,b))continue;
		
		int anc = getlca(a,b);
		focus(a,anc,ecs[e]);
		focus(b,anc,ecs[e]);
	}
	
	rep(i,m)printf("%lld\n",ans[i]);
	
	return 0;
}
```