#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz) : data(sz, -1) {}

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

struct edge1
{
  int u, v, cost, idx;

  bool operator<(const edge1 &e) const
  {
    return (cost < e.cost);
  }
};

struct edge2
{
  int to, cost, idx;
};

int N, M, A[200000], B[200000], C[200000];
vector< edge1 > edges;
bool killed[200000];
vector< edge2 > tree[100000], g[100000];
int64 all, ans[200000];
set< pair< int, int > > component[100000];

void rec(int idx, int par = -1)
{
  for(auto &e : g[idx]) {
    component[idx].emplace(e.cost, e.idx);
  }

  for(auto &e : tree[idx]) {
    if(e.to == par) continue;
    rec(e.to, idx);

    auto &u = component[idx], &v = component[e.to];

    if(!v.empty()) {
      ans[e.idx] = all;
      ans[e.idx] -= e.cost;
      ans[e.idx] += v.begin()->first;
    }
    if(u.size() < v.size()) swap(u, v);

    while(!v.empty()) {
      auto p = v.begin();
      if(u.count(*p)) u.erase(*p);
      else u.emplace(*p);
      v.erase(p);
    }
  }
}

int main()
{
  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++) {
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
    --A[i], --B[i];
    edges.push_back((edge1) {A[i], B[i], C[i], i});
  }

  UnionFind uf(N);
  sort(begin(edges), end(edges));
  for(auto &e : edges) {
    if(uf.unite(e.v, e.u)) {
      killed[e.idx] = true;
      all += e.cost;
    }
  }

  if(uf.size(0) != N) {
    for(int i = 0; i < M; i++) puts("-1");
    return (0);
  }

  for(int i = 0; i < M; i++) {
    if(killed[i]) {
      tree[A[i]].emplace_back((edge2) {B[i], C[i], i});
      tree[B[i]].emplace_back((edge2) {A[i], C[i], i});
      ans[i] = -1;
    } else {
      g[A[i]].emplace_back((edge2) {B[i], C[i], i});
      g[B[i]].emplace_back((edge2) {A[i], C[i], i});
      ans[i] = all;
    }
  }

  rec(0);

  for(int i = 0; i < M; i++) {
    printf("%lld\n", ans[i]);
  }
}
### 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>

using namespace std;

using int64 = long long;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz) : data(sz, -1) {}

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

struct edge1
{
  int u, v, cost, idx;

  bool operator<(const edge1 &e) const
  {
    return (cost < e.cost);
  }
};

struct edge2
{
  int to, cost, idx;
};

int N, M, A[200000], B[200000], C[200000];
vector< edge1 > edges;
bool killed[200000];
vector< edge2 > tree[100000], g[100000];
int64 all, ans[200000];
set< pair< int, int > > component[100000];

void rec(int idx, int par = -1)
{
  for(auto &e : g[idx]) {
    component[idx].emplace(e.cost, e.idx);
  }

  for(auto &e : tree[idx]) {
    if(e.to == par) continue;
    rec(e.to, idx);

    auto &u = component[idx], &v = component[e.to];

    if(!v.empty()) {
      ans[e.idx] = all;
      ans[e.idx] -= e.cost;
      ans[e.idx] += v.begin()->first;
    }
    if(u.size() < v.size()) swap(u, v);

    while(!v.empty()) {
      auto p = v.begin();
      if(u.count(*p)) u.erase(*p);
      else u.emplace(*p);
      v.erase(p);
    }
  }
}

int main()
{
  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++) {
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
    --A[i], --B[i];
    edges.push_back((edge1) {A[i], B[i], C[i], i});
  }

  UnionFind uf(N);
  sort(begin(edges), end(edges));
  for(auto &e : edges) {
    if(uf.unite(e.v, e.u)) {
      killed[e.idx] = true;
      all += e.cost;
    }
  }

  if(uf.size(0) != N) {
    for(int i = 0; i < M; i++) puts("-1");
    return (0);
  }

  for(int i = 0; i < M; i++) {
    if(killed[i]) {
      tree[A[i]].emplace_back((edge2) {B[i], C[i], i});
      tree[B[i]].emplace_back((edge2) {A[i], C[i], i});
      ans[i] = -1;
    } else {
      g[A[i]].emplace_back((edge2) {B[i], C[i], i});
      g[B[i]].emplace_back((edge2) {A[i], C[i], i});
      ans[i] = all;
    }
  }

  rec(0);

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