#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct edge {
	int from, to, id;
	ll cost;
	edge(int f, int t, int i, ll c) : from(f), to(t), id(i), cost(c) {}
	bool operator<(const edge& that) const {
		return cost < that.cost;
	}
};

using edges = vector<edge>;

class union_find {
	vector<int> par;
	int find(int a) {
		return par[a] < 0 ? a : par[a] = find(par[a]);
	}
public:
	union_find(int n) : par(n, -1) {}
	bool same(int a, int b) {
		return find(a) == find(b);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (par[a] < par[b]) swap(a, b);
		else if (par[a] == par[b]) par[b]--;
		par[a] = b;
	}
};

class HLD {
	vector<vector<int>> G;
	vector<int> vid, head, heavy, par, dep;
	int dfs(int v, int prev) {
		par[v] = prev;
		int cnt = 1, ma = 0;
		for (int to : G[v]) if (to != prev) {
			dep[to] = dep[v] + 1;
			int c = dfs(to, v);
			cnt += c;
			if (ma < c) {
				ma = c;
				heavy[v] = to;
			}
		}
		return cnt;
	}
public:
	HLD(int n) : G(n), vid(n, -1), head(n), heavy(n, -1), par(n), dep(n) {}
	void add(int u, int v) {
		G[u].push_back(v);
		G[v].push_back(u);
	}
	void build() {
		dfs(0, -1);
		int k = 0;
		queue<int> q;
		q.push(0);
		while (!q.empty()) {
			int h = q.front(); q.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				vid[i] = k++;
				head[i] = h;
				for (int j : G[i]) if (j != par[i] && j != heavy[i]) q.push(j);
			}
		}
	}
	int operator[](int v) {
		return vid[v];
	}
	void for_each_edge(int u, int v, function<void(int, int)> f) {
		while (true) {
			if (vid[u] > vid[v]) swap(u, v);
			if (head[u] != head[v]) {
				f(vid[head[v]], vid[v]);
				v = par[head[v]];
			}
			else {
				if (u != v) f(vid[u] + 1, vid[v]);
				break;
			}
		}
	}
};

struct ru {
	using type = int;
	static type id() { return INT_MAX; }
	static type up(type m, type u) { return min(m, u); }
};

template <typename M>
class segment_tree {
	using T = typename M::type;
	int size(int x) {
		int res = 1;
		while (res < x) res <<= 1;
		return res;
	}
	const int n;
	vector<T> data;
	void sub(int l, int r, T val, int node, int lb, int ub) {
		if (r <= lb || ub <= l) return;
		if (l <= lb && ub <= r) {
			data[node] = M::up(data[node], val);
			return;
		}
		int m = (lb + ub) >> 1;
		data[node << 1] = M::up(data[node << 1], data[node]);
		data[(node << 1) | 1] = M::up(data[(node << 1) | 1], data[node]);
		sub(l, r, val, node << 1, lb, m);
		sub(l, r, val, (node << 1) | 1, m, ub);
	}
	T get(int p, int node, int lb, int ub) {
		if (ub - lb == 1) return data[node];
		int m = (lb + ub) >> 1;
		if (p < m) {
			data[node << 1] = M::up(data[node << 1], data[node]);
			return get(p, node << 1, lb, m);
		}
		data[(node << 1) | 1] = M::up(data[(node << 1) | 1], data[node]);
		return get(p, (node << 1) | 1, m, ub);
	}
public:
	segment_tree(int n_) : n(size(n_)), data(n * 2, M::id()) {}
	void update(int l, int r, T val) {
		sub(l, r, val, 1, 0, n);
	}
	T find(int p) {
		return get(p, 1, 0, n);
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m;
	cin >> n >> m;
	edges es;
	for (int i = 0; i < m; i++) {
		int a, b;
		ll w;
		cin >> a >> b >> w; a--, b--;
		es.emplace_back(a, b, i, w);
	}
	sort(es.begin(), es.end());
	union_find uf(n);
	vector<int> used(m);
	ll sum = 0;
	HLD hl(n);
	for (int i = 0; i < m; i++) {
		int u = es[i].from, v = es[i].to, c = es[i].cost;
		if (!uf.same(u, v)) {
			used[i] = 1;
			uf.unite(u, v);
			sum += c;
			hl.add(u, v);
		}
	}
	if (count(used.begin(), used.end(), 1) != n - 1) {
		for (int i = 0; i < m; i++) {
			puts("-1");
		}
		return 0;
	}
	hl.build();
	segment_tree<ru> st(n + 1);
	for (int i = 0; i < m; i++) {
		if (!used[i]) {
			int u = es[i].from, v = es[i].to, c = es[i].cost;
			hl.for_each_edge(u, v, [&](int l, int r) {
				st.update(l, r + 1, c);
			});
		}
	}
	vector<ll> res(m);
	for (int i = 0; i < m; i++) {
		if (!used[i]) {
			res[es[i].id] = sum;
			continue;
		}
		ll cost = INT_MAX;
		hl.for_each_edge(es[i].from, es[i].to, [&](int l, int r) {
			cost = min(cost, (ll)st.find(l));
		});
		if (cost == INT_MAX) {
			res[es[i].id] = -1;
		}
		else {
			res[es[i].id] = sum + cost - es[i].cost;
		}
	}
	for (int i = 0; i < m; i++) {
		printf("%lld\n", res[i]);
	}
	return 0;
}


### Prompt

Your challenge is to write 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 <bits/stdc++.h>
using namespace std;
using ll = long long;

struct edge {
	int from, to, id;
	ll cost;
	edge(int f, int t, int i, ll c) : from(f), to(t), id(i), cost(c) {}
	bool operator<(const edge& that) const {
		return cost < that.cost;
	}
};

using edges = vector<edge>;

class union_find {
	vector<int> par;
	int find(int a) {
		return par[a] < 0 ? a : par[a] = find(par[a]);
	}
public:
	union_find(int n) : par(n, -1) {}
	bool same(int a, int b) {
		return find(a) == find(b);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (par[a] < par[b]) swap(a, b);
		else if (par[a] == par[b]) par[b]--;
		par[a] = b;
	}
};

class HLD {
	vector<vector<int>> G;
	vector<int> vid, head, heavy, par, dep;
	int dfs(int v, int prev) {
		par[v] = prev;
		int cnt = 1, ma = 0;
		for (int to : G[v]) if (to != prev) {
			dep[to] = dep[v] + 1;
			int c = dfs(to, v);
			cnt += c;
			if (ma < c) {
				ma = c;
				heavy[v] = to;
			}
		}
		return cnt;
	}
public:
	HLD(int n) : G(n), vid(n, -1), head(n), heavy(n, -1), par(n), dep(n) {}
	void add(int u, int v) {
		G[u].push_back(v);
		G[v].push_back(u);
	}
	void build() {
		dfs(0, -1);
		int k = 0;
		queue<int> q;
		q.push(0);
		while (!q.empty()) {
			int h = q.front(); q.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				vid[i] = k++;
				head[i] = h;
				for (int j : G[i]) if (j != par[i] && j != heavy[i]) q.push(j);
			}
		}
	}
	int operator[](int v) {
		return vid[v];
	}
	void for_each_edge(int u, int v, function<void(int, int)> f) {
		while (true) {
			if (vid[u] > vid[v]) swap(u, v);
			if (head[u] != head[v]) {
				f(vid[head[v]], vid[v]);
				v = par[head[v]];
			}
			else {
				if (u != v) f(vid[u] + 1, vid[v]);
				break;
			}
		}
	}
};

struct ru {
	using type = int;
	static type id() { return INT_MAX; }
	static type up(type m, type u) { return min(m, u); }
};

template <typename M>
class segment_tree {
	using T = typename M::type;
	int size(int x) {
		int res = 1;
		while (res < x) res <<= 1;
		return res;
	}
	const int n;
	vector<T> data;
	void sub(int l, int r, T val, int node, int lb, int ub) {
		if (r <= lb || ub <= l) return;
		if (l <= lb && ub <= r) {
			data[node] = M::up(data[node], val);
			return;
		}
		int m = (lb + ub) >> 1;
		data[node << 1] = M::up(data[node << 1], data[node]);
		data[(node << 1) | 1] = M::up(data[(node << 1) | 1], data[node]);
		sub(l, r, val, node << 1, lb, m);
		sub(l, r, val, (node << 1) | 1, m, ub);
	}
	T get(int p, int node, int lb, int ub) {
		if (ub - lb == 1) return data[node];
		int m = (lb + ub) >> 1;
		if (p < m) {
			data[node << 1] = M::up(data[node << 1], data[node]);
			return get(p, node << 1, lb, m);
		}
		data[(node << 1) | 1] = M::up(data[(node << 1) | 1], data[node]);
		return get(p, (node << 1) | 1, m, ub);
	}
public:
	segment_tree(int n_) : n(size(n_)), data(n * 2, M::id()) {}
	void update(int l, int r, T val) {
		sub(l, r, val, 1, 0, n);
	}
	T find(int p) {
		return get(p, 1, 0, n);
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m;
	cin >> n >> m;
	edges es;
	for (int i = 0; i < m; i++) {
		int a, b;
		ll w;
		cin >> a >> b >> w; a--, b--;
		es.emplace_back(a, b, i, w);
	}
	sort(es.begin(), es.end());
	union_find uf(n);
	vector<int> used(m);
	ll sum = 0;
	HLD hl(n);
	for (int i = 0; i < m; i++) {
		int u = es[i].from, v = es[i].to, c = es[i].cost;
		if (!uf.same(u, v)) {
			used[i] = 1;
			uf.unite(u, v);
			sum += c;
			hl.add(u, v);
		}
	}
	if (count(used.begin(), used.end(), 1) != n - 1) {
		for (int i = 0; i < m; i++) {
			puts("-1");
		}
		return 0;
	}
	hl.build();
	segment_tree<ru> st(n + 1);
	for (int i = 0; i < m; i++) {
		if (!used[i]) {
			int u = es[i].from, v = es[i].to, c = es[i].cost;
			hl.for_each_edge(u, v, [&](int l, int r) {
				st.update(l, r + 1, c);
			});
		}
	}
	vector<ll> res(m);
	for (int i = 0; i < m; i++) {
		if (!used[i]) {
			res[es[i].id] = sum;
			continue;
		}
		ll cost = INT_MAX;
		hl.for_each_edge(es[i].from, es[i].to, [&](int l, int r) {
			cost = min(cost, (ll)st.find(l));
		});
		if (cost == INT_MAX) {
			res[es[i].id] = -1;
		}
		else {
			res[es[i].id] = sum + cost - es[i].cost;
		}
	}
	for (int i = 0; i < m; i++) {
		printf("%lld\n", res[i]);
	}
	return 0;
}


```