#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
 
using namespace std;
 
#define MAX_N (100000)

#define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));

#define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);
 
typedef long long lint;
 
struct Edge {
	int from, to, id;
	lint cost;
	bool inMST;
	Edge(int from, int to, lint cost, int id) : from(from), to(to), cost(cost), id(id){inMST = false;}
	Edge(){}
};
 
vector<Edge> G[MAX_N], v;
 
bool operator < (const Edge &a, const Edge &b)
{
	return (a.cost < b.cost);
}
 
bool operator > (const Edge &a, const Edge &b)
{
	return (b < a);
}
 
int par[MAX_N];
 
void init()
{
	for (int i = 0; i < MAX_N; i++)
		par[i] = i;
}
 
int find(int x)
{
	if (x == par[x]) return (x);
	return (par[x] = find(par[x]));
}
 
void unite(int u, int v)
{
	u = find(u); v = find(v);
	if (u == v) return;
	int x = u ^ v;
	x ^= ((rand() & 1) ? u : v);
	par[x] = x ^ u ^ v;
}
 
bool same(int u, int v)
{
	return (find(u) == find(v));
}
 
lint ans[MAX_N * 2];
int ord[MAX_N], dst[MAX_N], low[MAX_N];
bool vis[MAX_N];
 
void predfs(int u, int p, int &k)
{
	ord[u] = low[u] = k++;
	vis[u] = true;
	
	for (int i = 0; i < G[u].size(); i++){
		if (!vis[G[u][i].to] && v[G[u][i].id].inMST){
			predfs(G[u][i].to, u, k);
			low[u] = min(low[u], low[G[u][i].to]);
		}
		else if (G[u][i].to != p) low[u] = min(low[u], ord[G[u][i].to]);
	}
	
	dst[u] = k++;
}
 
typedef priority_queue<Edge, vector<Edge>, greater<Edge> > PQ;
 
PQ pool[MAX_N];
int id[MAX_N];
lint pCost[MAX_N], cost;
PQ *pp[MAX_N], *qq;
 
void dfs(int u, int p)
{
	pp[u] = &pool[u];
	
	for (int i = 0; i < G[u].size(); i++){
		if (G[u][i].to != p && v[G[u][i].id].inMST){
			pCost[G[u][i].to] = G[u][i].cost; id[G[u][i].to] = G[u][i].id;
			dfs(G[u][i].to, u);
			qq = pp[G[u][i].to];
			if (pp[u]->size() < qq->size()) swap(pp[u], qq);
			while (qq->size()){
				pp[u]->push(qq->top()); qq->pop();
			}
		}
		else if (G[u][i].to != p && !(ord[u] <= ord[G[u][i].to] && dst[G[u][i].to] <= dst[u])){
			pp[u]->push(G[u][i]);
		}
	}
	
	while (pp[u]->size() && ord[u] <= ord[pp[u]->top().to] && dst[pp[u]->top().to] <= dst[u])
		pp[u]->pop();
	
	if (!pp[u]->size()){
		if (~p) ans[id[u]] = -1;
	}
	else {
		if (~p) ans[id[u]] = cost - pCost[u] + pp[u]->top().cost;
	}
	
}
 
int main()
{
	int n, m;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++){
		int a, b, w;
		scanf("%d %d %d", &a, &b, &w);
		G[--a].push_back(Edge(-1, --b, w, i));
		G[b].push_back(Edge(-1, a, w, i));
		v.push_back(Edge(a, b, w, i));
	}
	
	sort(v.begin(), v.end());
	
	init();
	
	int eNum = 0;
	for (int i = 0; i < v.size(); i++){
		if (!same(v[i].from, v[i].to)){
			unite(v[i].from, v[i].to);
			cost += v[i].cost;
			eNum++;
			v[v[i].id].inMST= true;
		}
	}
	
	if (eNum != n - 1) for (int i = 0; i < m; i++) printf("-1\n");
	else {
		for (int i = 0; i < m; i++){
			if (!v[i].inMST) ans[i] = cost;
		}
		int k = 0;
		
		BEGIN_STACK_EXTEND(128 * 1024 * 1024);
		predfs(0, -1, k);
		dfs(0, -1);
		END_STACK_EXTEND(128 * 1024 * 1024);

		for (int i = 0; i < m; i++){
			printf("%lld\n", ans[i]);
		}
	}
	
	return (0);
}
### Prompt

Your task is to create a CPP solution to 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 <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
 
using namespace std;
 
#define MAX_N (100000)

#define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));

#define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);
 
typedef long long lint;
 
struct Edge {
	int from, to, id;
	lint cost;
	bool inMST;
	Edge(int from, int to, lint cost, int id) : from(from), to(to), cost(cost), id(id){inMST = false;}
	Edge(){}
};
 
vector<Edge> G[MAX_N], v;
 
bool operator < (const Edge &a, const Edge &b)
{
	return (a.cost < b.cost);
}
 
bool operator > (const Edge &a, const Edge &b)
{
	return (b < a);
}
 
int par[MAX_N];
 
void init()
{
	for (int i = 0; i < MAX_N; i++)
		par[i] = i;
}
 
int find(int x)
{
	if (x == par[x]) return (x);
	return (par[x] = find(par[x]));
}
 
void unite(int u, int v)
{
	u = find(u); v = find(v);
	if (u == v) return;
	int x = u ^ v;
	x ^= ((rand() & 1) ? u : v);
	par[x] = x ^ u ^ v;
}
 
bool same(int u, int v)
{
	return (find(u) == find(v));
}
 
lint ans[MAX_N * 2];
int ord[MAX_N], dst[MAX_N], low[MAX_N];
bool vis[MAX_N];
 
void predfs(int u, int p, int &k)
{
	ord[u] = low[u] = k++;
	vis[u] = true;
	
	for (int i = 0; i < G[u].size(); i++){
		if (!vis[G[u][i].to] && v[G[u][i].id].inMST){
			predfs(G[u][i].to, u, k);
			low[u] = min(low[u], low[G[u][i].to]);
		}
		else if (G[u][i].to != p) low[u] = min(low[u], ord[G[u][i].to]);
	}
	
	dst[u] = k++;
}
 
typedef priority_queue<Edge, vector<Edge>, greater<Edge> > PQ;
 
PQ pool[MAX_N];
int id[MAX_N];
lint pCost[MAX_N], cost;
PQ *pp[MAX_N], *qq;
 
void dfs(int u, int p)
{
	pp[u] = &pool[u];
	
	for (int i = 0; i < G[u].size(); i++){
		if (G[u][i].to != p && v[G[u][i].id].inMST){
			pCost[G[u][i].to] = G[u][i].cost; id[G[u][i].to] = G[u][i].id;
			dfs(G[u][i].to, u);
			qq = pp[G[u][i].to];
			if (pp[u]->size() < qq->size()) swap(pp[u], qq);
			while (qq->size()){
				pp[u]->push(qq->top()); qq->pop();
			}
		}
		else if (G[u][i].to != p && !(ord[u] <= ord[G[u][i].to] && dst[G[u][i].to] <= dst[u])){
			pp[u]->push(G[u][i]);
		}
	}
	
	while (pp[u]->size() && ord[u] <= ord[pp[u]->top().to] && dst[pp[u]->top().to] <= dst[u])
		pp[u]->pop();
	
	if (!pp[u]->size()){
		if (~p) ans[id[u]] = -1;
	}
	else {
		if (~p) ans[id[u]] = cost - pCost[u] + pp[u]->top().cost;
	}
	
}
 
int main()
{
	int n, m;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++){
		int a, b, w;
		scanf("%d %d %d", &a, &b, &w);
		G[--a].push_back(Edge(-1, --b, w, i));
		G[b].push_back(Edge(-1, a, w, i));
		v.push_back(Edge(a, b, w, i));
	}
	
	sort(v.begin(), v.end());
	
	init();
	
	int eNum = 0;
	for (int i = 0; i < v.size(); i++){
		if (!same(v[i].from, v[i].to)){
			unite(v[i].from, v[i].to);
			cost += v[i].cost;
			eNum++;
			v[v[i].id].inMST= true;
		}
	}
	
	if (eNum != n - 1) for (int i = 0; i < m; i++) printf("-1\n");
	else {
		for (int i = 0; i < m; i++){
			if (!v[i].inMST) ans[i] = cost;
		}
		int k = 0;
		
		BEGIN_STACK_EXTEND(128 * 1024 * 1024);
		predfs(0, -1, k);
		dfs(0, -1);
		END_STACK_EXTEND(128 * 1024 * 1024);

		for (int i = 0; i < m; i++){
			printf("%lld\n", ans[i]);
		}
	}
	
	return (0);
}
```