メモ: この問題は AWC-E として発展的な難易度であると思われます。本解説の筆者はこの問題を ABC の難しい F 問題から易しい G 問題程度の難易度であると考えています。

青木君が辺を切らなかった場合、この問題は最小全域木問題そのものです。このときの最小全域木を \(T\) と呼びます。
青木君が \(T\) に含まれる辺を切らなかった場合、高橋君は \(T\) をそのまま作ることになるので辺を切る意味がありません。
よって、青木君は必ず \(T\) の辺のうちいずれかを切ることになります。
また、高橋君の辺の採用の方法のうち、青木君が切らなかった \(N-2\) 本の \(T\) の辺全て(この辺集合を \(T^-\) と呼びます)を採用する方法があることが証明できます。

証明:
高橋君が採用した全域木 \(X\) に \(T^-\) のうち何らかの辺 \(e\) が含まれていないとします。
\(X\) に \(e\) を加えてできた閉路 \(C\) を考えます。 \(e\) は元々の最小全域木 \(T\) に含まれている辺であるので、 \(C\) 中に重みが \(e\) 以上の \(e\) でない辺 \(f\) が存在することが分かります。
さらに、最小全域木の定義より \(f\) は \(T\) 外から選択できることも分かります。
すると、 \(X\) から \(f\) を除去して \(e\) を加えることで解が悪化しません。

これで、ゲームは以下の形になることが分かりました。

• 高橋君が最小全域木 \(T\) を作り、コストを支払う。
• 青木君が、最小全域木 \(T\) 内のいずれかの辺を切る。切った辺のコストは高橋君に返金する。
• すると、 \(T\) は \(2\) つの連結成分に分かれる。
• 高橋君が新たな辺を \(1\) 本追加して、最小のコストでこれらの連結成分を繋ぐ。

さて、これで下準備が整いました。この問題を実際に解いていきましょう。

• \(T\) に含まれない辺 \(e\) それぞれについて、以下を行う。
  • \(T\) に \(e\) を追加することで閉路ができるが、 \(e\) はこの閉路に含まれる \(T\) 中の辺を切られた時、またその時にのみ有用である。
  • よって、 \(T\) 中のそのような辺全てに対して \(e\) のコストで置き換えられることを記録しておく。★
• その後、 \(T\) に含まれる辺 \(e\) 全てにわたる、以下の 最大値 が答えである。
  • 青木君が \(e\) を切った場合を考える。このとき、高橋君は \(e\) を切った場合の 最小 のコストで置き換える。

難しいのは★の部分です。 \(T\) に辺 \(e=(u,v)\) を追加してできる閉路は、 \(e\) に \(T\) の \(u-v\) パスを加えたものです。
このように、木の特定のパスに対して情報を記録したい場合には、 HL分解 (Heavy-Light Decomposition / 重軽分解) が有用です。

ここに最小値を区間更新する Lazy Segtree を組み合わせることで、パスに対する情報更新を \(O(\log N)\) 個の区間に対する情報更新に言い換えることができます。

Lazy Segtree 自体の時間計算量が \(O(\log N)\) かかるため、全体で時間計算量 \(O(N \log^2 N)\) 程度の解法を得ることになります。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

using Graph=vector<vector<int>>;
using pi=pair<int,int>;
using ll=long long;

int op(int l,int r){return min(l,r);}
int e(){return 2e9;}
int mapping(int l,int r){return min(l,r);}
int composition(int l,int r){return min(l,r);}
int id(){return 2e9;}

struct HLD{
  vector<int> pareg;
  vector<int> backeg;
  vector<int> dep;
  int cureg;
  vector<int> topv;
  vector<int> tope;
  bool vwei; // true: vertex-weighted, false: edge-weighted

  HLD(int n,Graph &g,bool vw,int root=0){
    vwei=vw;

    dfs1(root,-1,g);

    pareg.resize(n);
    backeg.resize(n);
    dep.resize(n);
    topv.resize(n);
    tope.resize(n);

    cureg=1;
    pareg[root]=0;
    topv[0]=-1;
    tope[0]=0;

    dfs2(root,-1,0,true,g);
  }

  int dfs1(int v,int pv,Graph &g){
    int res=1;
    int uid=-1,umax=-1;
    for(int i=0;i<g[v].size();i++){
      if(g[v][i]==pv){continue;}

      int und=dfs1(g[v][i],v,g);
      res+=und;
      if(umax<und){
        umax=und;
        uid=i;
      }
    }
    if(uid>0){
      swap(g[v][uid],g[v][0]);
    }
    return res;
  }

  void dfs2(int v,int pv,int cdep,bool upheav,Graph &g){
    dep[v]=cdep;

    for(int i=0;i<g[v].size();i++){
      if(g[v][i]==pv){continue;}

      if(i==0){
        // heavy
        if(upheav){
          topv[cureg]=topv[pareg[v]];
          tope[cureg]=tope[pareg[v]];
        }
        else{
          topv[cureg]=v;
          tope[cureg]=cureg;
        }

        pareg[g[v][i]]=cureg;
        cureg++;
        dfs2(g[v][i],v,cdep+1,true,g);
      }
      else{
        // light
        topv[cureg]=v;
        tope[cureg]=cureg;

        pareg[g[v][i]]=cureg;
        cureg++;
        dfs2(g[v][i],v,cdep+1,false,g);
      }
    }

    backeg[v]=cureg;
  }

  // single vertex (for vertex-weighted)
  int single(int v){
    return pareg[v];
  }

  // subtree is [l,r]
  pi subtree(int v){
    if(vwei){
      return {pareg[v],backeg[v]-1};
    }
    else{
      return {pareg[v]+1,backeg[v]-1};
    }
  }

  // u->v path is {[l0,r0], [l1,r1], ...}
  // each segments may reversed (so li<=ri may NOT be satisfied)
  vector<pi> path(int u,int v){
    vector<pi> uu;
    vector<pi> vv;
    while(u!=v){
      if(tope[pareg[u]]==tope[pareg[v]]){ // same path
        if(dep[u]>dep[v]){
          // u goes up
          uu.push_back({pareg[u],pareg[u]-(dep[u]-dep[v]-1)});
          u=v;
        }
        else{
          // v goes up
          vv.push_back({pareg[v],pareg[v]-(dep[v]-dep[u]-1)});
          v=u;
        }
        break;
      }

      int du=-1;
      int dv=-1;
      if(topv[pareg[u]]>=0){du=dep[topv[pareg[u]]];}
      if(topv[pareg[v]]>=0){dv=dep[topv[pareg[v]]];}

      if(du>dv){
        // u goes up
        uu.push_back({pareg[u],tope[pareg[u]]});
        u=topv[pareg[u]];
      }
      else{
        // v goes up
        vv.push_back({pareg[v],tope[pareg[v]]});
        v=topv[pareg[v]];
      }
    }

    vector<pi> res;
    for(auto &nx : uu){
      res.push_back(nx);
    }
    if(vwei){
      res.push_back({pareg[u],pareg[u]});
    }
    reverse(vv.begin(),vv.end());
    for(auto &nx : vv){
      swap(nx.first,nx.second);
      res.push_back(nx);
    }
    return res;
  }
};

int main(){
  int N,M;
  cin >> N >> M;
  vector<array<int,3>> edge(M);
  for(int i=0;i<M;i++){
    cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
    edge[i][1]--; edge[i][2]--;
  }
  sort(edge.begin(),edge.end());

  ll mw=0;
  dsu ds(N);
  Graph mst(N);
  vector<array<int,3>> mse;
  vector<array<int,3>> other;
  for(auto &nx : edge){
    if(ds.same(nx[1],nx[2])){
      other.push_back(nx);
    }
    else{
      mse.push_back(nx);
      mst[nx[1]].push_back(nx[2]);
      mst[nx[2]].push_back(nx[1]);
      ds.merge(nx[1],nx[2]);
      mw+=nx[0];
    }
  }
  HLD hld(N,mst,false);
  lazy_segtree<int, op, e, int, mapping, composition, id> seg(N);
  for(auto &nx : other){
    auto pt=hld.path(nx[1],nx[2]);
    for(auto &ny : pt){
      if(ny.first>ny.second){swap(ny.first,ny.second);}
      seg.apply(ny.first,ny.second+1,nx[0]);
    }
  }
  ll res=0;
  for(auto &nx : mse){
    auto ps=hld.path(nx[1],nx[2]);
    ll cres=mw;
    cres-=nx[0];
    cres+=seg.get(min(ps[0].first,ps[0].second));
    res=max(res,cres);
  }
  cout << res << "\n";
  return 0;
}