#include <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}

#define rank Asdfiasofsad
class UF{
public:
  int V;
  vector<int> par,rank;
  UF(){}
  UF(int V):V(V),par(V),rank(V,0){for(int i=0;i<V;i++)par[i]=i;}
  
  int find(int x){
    assert(x < V);
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
  }
  
  void unite(int x,int y){
    x=find(x), y=find(y);
    if(x==y)return;
    if(rank[x]<rank[y])par[x]=y;
    else{
      par[y]=x;
      if(rank[x]==rank[y])rank[x]++;
    }
  }

  bool same(int x,int y){return find(x)==find(y);}
};

class RMQ2{
public : 
  typedef long long ll;
  struct data{
    bool type; //0 - empty   , 1 - update
    ll value;
  };
  ll n;
  vector<ll> dat;
  vector<data> td;
  
  RMQ2(){n=-1;}
  RMQ2(int n_){
    n=1;
    while(n<n_)n*=2;
    td.resize(2*n-1,(data){0,0});
    dat.resize(2*n-1,INF);
  }
  
  //[a,b)?????????x????????´???update(a,b,x)
  ll update(int a,int b,int x,bool flg=true,int k=0,int l=0,int r=-1){
    if(r==-1) r=n, assert(a < n && b <= n);
    if(r<=a||b<=l)return flg? dat[k]:INF;
    if(a<=l&&r<=b){
      if(flg==true){
        td[k]=(data){1,x};
        dat[k]=x;
      }
      return dat[k];
    }
    
    if(td[k].type){
      dat[k*2+1]=dat[k*2+2]=td[k].value;
      td[k*2+1]=td[k*2+2]=(data){1,td[k].value};
      td[k].type=0;
    }
    
    ll vl=update(a,b,x,flg,k*2+1,l,(l+r)/2);
    ll vr=update(a,b,x,flg,k*2+2,(l+r)/2,r);
    if(flg==true)dat[k]=min(vl,vr);
    return min(vl,vr);
  }
  
  //[a,b)???????°????????????????find(a,b);
  ll find(int a,int b){return update(a,b,0,false);};
};

class HLD{
public:
  int V;                     //???????????°
  int root;                  //??????????????????
  vector<vector<int> > G;    //Grapth
  vector<int> par;           //parent: par[??????????????????]->??????????????????
  vector<int> Hchild;        //???????????????????????????Heavy Child???????????????: Hedge[??????????????????]->??????????????????
  vector<int> number;        //???????????????????????????????????????????????????: number[??????????????????]->????????´??????????????????
  vector<int> id;            //??????????????´????????°???????????????????????????: id[????????´??????????????????]->??????????????????
  vector<int> group;         //???????????????????±?????????°???????????????: group[??????????????????]->??????????????????
  vector<int> depth;         //?????????????????????????????±???: depth[??????????????????]
  bool ok;                   //build()???????????§?????????
  
  HLD(){root = V = -1;}
  HLD(int V):V(V), root(0), G(V), par(V,-1), Hchild(V,-1), 
             number(V,-1),id(V,-1),group(V,-1),depth(V,0),ok(false){}
  
  void add_edge(int a,int b){
    assert(a < V && b < V);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  void build(int _root = 0){
    root = _root;
    int num = 0;
    ok = true;
    dfs1(); numbering(num); dfs2();
  }

  int dfs1(int pos = -1,int pre = -1){
    if(pos == -1) pos = root;
    int mx = -1, weight = 1;
    for(int to:G[pos]){
      if(to == pre) continue;
      int cweight = dfs1(to,pos);
      weight += cweight;
      if(mx < cweight) Hchild[pos] = to, mx = cweight;
    }
    return weight;
  }
  
  void dfs2(int pos = -1,int pre = -1,int dep = 0,int g = -1){
    if(pos == -1) pos = g = root;
    par[pos] = pre;
    depth[pos] = dep;
    group[pos] = g;
    for(int to:G[pos]) if(to!=pre) dfs2(to,pos,dep+1,Hchild[pos]==to? g:to);
  }
  
  void numbering(int &cnt,int pos = -1,int pre = -1){
    if(pos == -1) pos = root;
    number[pos] = cnt++;
    id[number[pos]] = pos;
    if(Hchild[pos]>=0) numbering(cnt,Hchild[pos],pos);
    for(int to:G[pos])if(to!=pre && to!=Hchild[pos]) numbering(cnt,to,pos);
  }
  
  typedef pair<int,int> P;
  vector<P> paths;  //[u,v]???????????????????????????????????????????????£??????????????????????§£?????????(?????§logN???)
  vector<P> Ledges; //paths????£?????????¶???????????¨??????
  void buildPaths(int u,int v){
    if(depth[group[u]] < depth[group[v]]) swap(u,v);// ??±???????????????????????????????????????
    int nu=number[u], nv=number[v];
    if(same(u,v)){ paths.push_back(P(min(nu,nv),max(nu,nv)));return;} 

    int gu = group[u];
    buildPaths(par[gu],v);

    paths.push_back(P(number[gu], number[u]));
    Ledges.push_back(P(number[par[gu]], number[gu]));
  }
  
  pair<vector<P>, vector<P> > getPath(int u,int v){
    assert(ok && "Please Build");
    paths.clear();
    Ledges.clear();
    buildPaths(u,v);
    return make_pair(paths,Ledges);
  }

  /*(??????????????????,??????????????????)*/ 
  bool same(int a,int b){return group[a] == group[b];}
};

typedef pair<int,int> P;
typedef pair<P,P> PP;
int n,m;
vector<vector<int> >G;
vector<PP> edge;
vector<int> used;
HLD hld;
RMQ2 rmq;

int kuraskal(){
  sort(edge.begin(),edge.end());
  hld = HLD(n);      
  used.resize(m,0);
  UF U(n);
  int sum = 0,cnt = 0;
  for(int i=0;i<m;i++){
    int a = edge[i].second.first;
    int b = edge[i].second.second;
    int c = edge[i].first.first;
    if(U.same(a,b)) continue;
    cnt++;
    U.unite(a,b);
    hld.add_edge(a,b);
    used[i] = 1;
    sum += c;
  }
  if(cnt != n-1) return INF;
  return sum;
}


void build(){
  rmq = RMQ2(n);
  hld.build(rand()%n);
  for(int i=m-1;i>=0;i--){
    if(used[i]) continue;
    int a = edge[i].second.first;
    int b = edge[i].second.second;
    int c = edge[i].first.first;
    pair<vector<P>,vector<P> > path = hld.getPath(a,b);
    vector<P> &hpath = path.first, &ledge = path.second;
    if(hld.depth[a] > hld.depth[b]) swap(a,b);
    hpath[0].first++;
    for(P p:hpath) rmq.update(p.first,p.second+1,c);
    for(P e:ledge) rmq.update(e.second,e.second+1,c);
  }
}

signed main(){
  cin>>n>>m;
  G.resize(n);
  edge.resize(m);
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c; a--,b--;
    edge[i] = PP(P(c,i),P(a,b));
  }
 
  int mincost = kuraskal();
  build();
  vector<int> ans(m,mincost);  
  for(int i=0;i<m;i++){
    if(!used[i]) continue;
    int idx = edge[i].first.second;
    int a = edge[i].second.first;
    int b = edge[i].second.second;
    int c = edge[i].first.first;
    if(hld.depth[a] > hld.depth[b]) swap(a,b); 
    int c2 = rmq.find(hld.number[b],hld.number[b]+1);
    ans[idx] = mincost - c + c2;
  }

  for(int a:ans) cout<<(a>=INF? -1:a)<<endl;
  return 0;
}
### Prompt

Please provide a CPP coded solution 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 <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}

#define rank Asdfiasofsad
class UF{
public:
  int V;
  vector<int> par,rank;
  UF(){}
  UF(int V):V(V),par(V),rank(V,0){for(int i=0;i<V;i++)par[i]=i;}
  
  int find(int x){
    assert(x < V);
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
  }
  
  void unite(int x,int y){
    x=find(x), y=find(y);
    if(x==y)return;
    if(rank[x]<rank[y])par[x]=y;
    else{
      par[y]=x;
      if(rank[x]==rank[y])rank[x]++;
    }
  }

  bool same(int x,int y){return find(x)==find(y);}
};

class RMQ2{
public : 
  typedef long long ll;
  struct data{
    bool type; //0 - empty   , 1 - update
    ll value;
  };
  ll n;
  vector<ll> dat;
  vector<data> td;
  
  RMQ2(){n=-1;}
  RMQ2(int n_){
    n=1;
    while(n<n_)n*=2;
    td.resize(2*n-1,(data){0,0});
    dat.resize(2*n-1,INF);
  }
  
  //[a,b)?????????x????????´???update(a,b,x)
  ll update(int a,int b,int x,bool flg=true,int k=0,int l=0,int r=-1){
    if(r==-1) r=n, assert(a < n && b <= n);
    if(r<=a||b<=l)return flg? dat[k]:INF;
    if(a<=l&&r<=b){
      if(flg==true){
        td[k]=(data){1,x};
        dat[k]=x;
      }
      return dat[k];
    }
    
    if(td[k].type){
      dat[k*2+1]=dat[k*2+2]=td[k].value;
      td[k*2+1]=td[k*2+2]=(data){1,td[k].value};
      td[k].type=0;
    }
    
    ll vl=update(a,b,x,flg,k*2+1,l,(l+r)/2);
    ll vr=update(a,b,x,flg,k*2+2,(l+r)/2,r);
    if(flg==true)dat[k]=min(vl,vr);
    return min(vl,vr);
  }
  
  //[a,b)???????°????????????????find(a,b);
  ll find(int a,int b){return update(a,b,0,false);};
};

class HLD{
public:
  int V;                     //???????????°
  int root;                  //??????????????????
  vector<vector<int> > G;    //Grapth
  vector<int> par;           //parent: par[??????????????????]->??????????????????
  vector<int> Hchild;        //???????????????????????????Heavy Child???????????????: Hedge[??????????????????]->??????????????????
  vector<int> number;        //???????????????????????????????????????????????????: number[??????????????????]->????????´??????????????????
  vector<int> id;            //??????????????´????????°???????????????????????????: id[????????´??????????????????]->??????????????????
  vector<int> group;         //???????????????????±?????????°???????????????: group[??????????????????]->??????????????????
  vector<int> depth;         //?????????????????????????????±???: depth[??????????????????]
  bool ok;                   //build()???????????§?????????
  
  HLD(){root = V = -1;}
  HLD(int V):V(V), root(0), G(V), par(V,-1), Hchild(V,-1), 
             number(V,-1),id(V,-1),group(V,-1),depth(V,0),ok(false){}
  
  void add_edge(int a,int b){
    assert(a < V && b < V);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  void build(int _root = 0){
    root = _root;
    int num = 0;
    ok = true;
    dfs1(); numbering(num); dfs2();
  }

  int dfs1(int pos = -1,int pre = -1){
    if(pos == -1) pos = root;
    int mx = -1, weight = 1;
    for(int to:G[pos]){
      if(to == pre) continue;
      int cweight = dfs1(to,pos);
      weight += cweight;
      if(mx < cweight) Hchild[pos] = to, mx = cweight;
    }
    return weight;
  }
  
  void dfs2(int pos = -1,int pre = -1,int dep = 0,int g = -1){
    if(pos == -1) pos = g = root;
    par[pos] = pre;
    depth[pos] = dep;
    group[pos] = g;
    for(int to:G[pos]) if(to!=pre) dfs2(to,pos,dep+1,Hchild[pos]==to? g:to);
  }
  
  void numbering(int &cnt,int pos = -1,int pre = -1){
    if(pos == -1) pos = root;
    number[pos] = cnt++;
    id[number[pos]] = pos;
    if(Hchild[pos]>=0) numbering(cnt,Hchild[pos],pos);
    for(int to:G[pos])if(to!=pre && to!=Hchild[pos]) numbering(cnt,to,pos);
  }
  
  typedef pair<int,int> P;
  vector<P> paths;  //[u,v]???????????????????????????????????????????????£??????????????????????§£?????????(?????§logN???)
  vector<P> Ledges; //paths????£?????????¶???????????¨??????
  void buildPaths(int u,int v){
    if(depth[group[u]] < depth[group[v]]) swap(u,v);// ??±???????????????????????????????????????
    int nu=number[u], nv=number[v];
    if(same(u,v)){ paths.push_back(P(min(nu,nv),max(nu,nv)));return;} 

    int gu = group[u];
    buildPaths(par[gu],v);

    paths.push_back(P(number[gu], number[u]));
    Ledges.push_back(P(number[par[gu]], number[gu]));
  }
  
  pair<vector<P>, vector<P> > getPath(int u,int v){
    assert(ok && "Please Build");
    paths.clear();
    Ledges.clear();
    buildPaths(u,v);
    return make_pair(paths,Ledges);
  }

  /*(??????????????????,??????????????????)*/ 
  bool same(int a,int b){return group[a] == group[b];}
};

typedef pair<int,int> P;
typedef pair<P,P> PP;
int n,m;
vector<vector<int> >G;
vector<PP> edge;
vector<int> used;
HLD hld;
RMQ2 rmq;

int kuraskal(){
  sort(edge.begin(),edge.end());
  hld = HLD(n);      
  used.resize(m,0);
  UF U(n);
  int sum = 0,cnt = 0;
  for(int i=0;i<m;i++){
    int a = edge[i].second.first;
    int b = edge[i].second.second;
    int c = edge[i].first.first;
    if(U.same(a,b)) continue;
    cnt++;
    U.unite(a,b);
    hld.add_edge(a,b);
    used[i] = 1;
    sum += c;
  }
  if(cnt != n-1) return INF;
  return sum;
}


void build(){
  rmq = RMQ2(n);
  hld.build(rand()%n);
  for(int i=m-1;i>=0;i--){
    if(used[i]) continue;
    int a = edge[i].second.first;
    int b = edge[i].second.second;
    int c = edge[i].first.first;
    pair<vector<P>,vector<P> > path = hld.getPath(a,b);
    vector<P> &hpath = path.first, &ledge = path.second;
    if(hld.depth[a] > hld.depth[b]) swap(a,b);
    hpath[0].first++;
    for(P p:hpath) rmq.update(p.first,p.second+1,c);
    for(P e:ledge) rmq.update(e.second,e.second+1,c);
  }
}

signed main(){
  cin>>n>>m;
  G.resize(n);
  edge.resize(m);
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c; a--,b--;
    edge[i] = PP(P(c,i),P(a,b));
  }
 
  int mincost = kuraskal();
  build();
  vector<int> ans(m,mincost);  
  for(int i=0;i<m;i++){
    if(!used[i]) continue;
    int idx = edge[i].first.second;
    int a = edge[i].second.first;
    int b = edge[i].second.second;
    int c = edge[i].first.first;
    if(hld.depth[a] > hld.depth[b]) swap(a,b); 
    int c2 = rmq.find(hld.number[b],hld.number[b]+1);
    ans[idx] = mincost - c + c2;
  }

  for(int a:ans) cout<<(a>=INF? -1:a)<<endl;
  return 0;
}
```