#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
struct edge{
	int a,b;
	ll c;
	int id;
	edge(int x,int y,int z,int w):a(x),b(y),c(z),id(w){}
};
bool comp(const edge& x, const edge& y){
	return x.c<y.c;
}
int par[100000];
int find(int x){
	if(x==par[x]) return x;
	return par[x]=find(par[x]);
}
bool same(int x,int y){
	return find(x)==find(y);
}
void unite(int x,int y){
	par[find(x)]=find(y);
}

int N,M;
ll sum=0;
int o[100000];
set<P> st[100000];		//st[v] P(es[id].c,id)
vector<P> G[100000];
vector<int> oG[100000];
vector<edge> es;
ll ans[200000];
void dfs(int v,int p,int btw){
//	for(P pu:G[v]) if(pu.fs!=p) dfs(pu.fs,v,pu.sc);
	for(int i:oG[v]){
		st[v].insert(P(es[i].c,i));
	}
	int id=v;
	for(P u_:G[v]) if(u_.fs!=p){
		int u=o[u_.fs];
		if(st[id].size()<st[u].size()) swap(id,u);
		for(P pi:st[u]){
			if(st[id].find(pi)!=st[id].end()) st[id].erase(pi);
			else st[id].insert(pi);
		}
	}
	o[v]=id;
	if(v==0) return;
	if(st[id].empty()){
		ans[es[btw].id]=-1;
/*		show(v);
		show(p);
		show(id);
		assert(0);*/
	}else{
		ans[es[btw].id]=sum-es[btw].c+(*st[id].begin()).fs;
	}
}
int main(){
	cin>>N>>M;
	rep(i,N) par[i]=i;
	rep(i,M){
		int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		es.pb(edge(a,b,c,i));
	}
	sort(all(es),comp);
	int cnt=0;
	rep(i,M){
		edge e=es[i];
		if(same(e.a,e.b)){
			oG[e.a].pb(i);
			oG[e.b].pb(i);
			ans[e.id]=-2;
		}else{
			unite(e.a,e.b);
			sum+=e.c;
			cnt++;
			G[e.a].pb(P(e.b,i));
			G[e.b].pb(P(e.a,i));
		}
	}
	rep(i,M) if(ans[i]==-2) ans[i]=sum;
	if(cnt!=N-1){
		rep(i,M) puts("-1");
		return 0;
	}
	int pa[100000]={};
	queue<int> que;
	que.push(0);
	pa[0]=-1;
	vector<int> a,b,c;
	while(!que.empty()){
		int v=que.front();
		que.pop();
		for(P p:G[v]){
			if(p.fs==pa[v]) continue;
			a.pb(p.fs),b.pb(v),c.pb(p.sc);
			pa[p.fs]=v;
			que.push(p.fs);
		}
	}
	int K=a.size();
	rep(i,K) dfs(a[K-1-i],b[K-1-i],c[K-1-i]);
	rep(i,M) cout<<ans[i]<<endl;
}
### Prompt

Create a solution in Cpp for the following problem:

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 <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
struct edge{
	int a,b;
	ll c;
	int id;
	edge(int x,int y,int z,int w):a(x),b(y),c(z),id(w){}
};
bool comp(const edge& x, const edge& y){
	return x.c<y.c;
}
int par[100000];
int find(int x){
	if(x==par[x]) return x;
	return par[x]=find(par[x]);
}
bool same(int x,int y){
	return find(x)==find(y);
}
void unite(int x,int y){
	par[find(x)]=find(y);
}

int N,M;
ll sum=0;
int o[100000];
set<P> st[100000];		//st[v] P(es[id].c,id)
vector<P> G[100000];
vector<int> oG[100000];
vector<edge> es;
ll ans[200000];
void dfs(int v,int p,int btw){
//	for(P pu:G[v]) if(pu.fs!=p) dfs(pu.fs,v,pu.sc);
	for(int i:oG[v]){
		st[v].insert(P(es[i].c,i));
	}
	int id=v;
	for(P u_:G[v]) if(u_.fs!=p){
		int u=o[u_.fs];
		if(st[id].size()<st[u].size()) swap(id,u);
		for(P pi:st[u]){
			if(st[id].find(pi)!=st[id].end()) st[id].erase(pi);
			else st[id].insert(pi);
		}
	}
	o[v]=id;
	if(v==0) return;
	if(st[id].empty()){
		ans[es[btw].id]=-1;
/*		show(v);
		show(p);
		show(id);
		assert(0);*/
	}else{
		ans[es[btw].id]=sum-es[btw].c+(*st[id].begin()).fs;
	}
}
int main(){
	cin>>N>>M;
	rep(i,N) par[i]=i;
	rep(i,M){
		int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		es.pb(edge(a,b,c,i));
	}
	sort(all(es),comp);
	int cnt=0;
	rep(i,M){
		edge e=es[i];
		if(same(e.a,e.b)){
			oG[e.a].pb(i);
			oG[e.b].pb(i);
			ans[e.id]=-2;
		}else{
			unite(e.a,e.b);
			sum+=e.c;
			cnt++;
			G[e.a].pb(P(e.b,i));
			G[e.b].pb(P(e.a,i));
		}
	}
	rep(i,M) if(ans[i]==-2) ans[i]=sum;
	if(cnt!=N-1){
		rep(i,M) puts("-1");
		return 0;
	}
	int pa[100000]={};
	queue<int> que;
	que.push(0);
	pa[0]=-1;
	vector<int> a,b,c;
	while(!que.empty()){
		int v=que.front();
		que.pop();
		for(P p:G[v]){
			if(p.fs==pa[v]) continue;
			a.pb(p.fs),b.pb(v),c.pb(p.sc);
			pa[p.fs]=v;
			que.push(p.fs);
		}
	}
	int K=a.size();
	rep(i,K) dfs(a[K-1-i],b[K-1-i],c[K-1-i]);
	rep(i,M) cout<<ans[i]<<endl;
}
```