AT_abc355_f [ABC355F] MST Query

[problemUrl]: https://atcoder.jp/contests/abc355/tasks/abc355_f 頂点に $ 1 $ から $ N $ の番号が、辺に $ 1 $ から $ N-1 $ の番号が付いた $ N $ 頂点 $ N-1 $ 辺の重み付き無向連結グラフ $ G $ が与えられます。辺 $ i $ は頂点 $ a_i $ と頂点 $ b_i $ を結んでおり、その重みは $ c_i $ です。 $ Q $ 個のクエリが与えられるので順に処理してください。$ i $ 番目のクエリは以下で説明されます。 - 整数 $ u_i,v_i,w_i $ が与えられる。$ G $ の頂点 $ u_i,v_i $ の間に重み $ w_i $ の辺を追加する。その後、$ G $ の最小全域木に含まれる辺の重みの和を出力する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ a_1 $ $ b_1 $ $ c_1 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $ $ c_{N-1} $ $ u_1 $ $ v_1 $ $ w_1 $ $ \vdots $ $ u_Q $ $ v_Q $ $ w_Q $

$ Q $ 行出力せよ。$ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。

### 制約 - $ 2\leq\ N\leq\ 2\ \times\ 10^5 $ - $ 1\leq\ Q\leq\ 2\ \times\ 10^5 $ - $ 1\leq\ a_i\lt\ b_i\leq\ N $ - $ 1\leq\ u_i\lt\ v_i\leq\ N $ - $ 1\leq\ c_i,w_i\leq\ 10 $ - クエリを処理する前のグラフは連結 - 入力はすべて整数 ### Sample Explanation 1 各クエリで辺を追加した後のグラフを示しています。最小全域木に含まれる辺は赤色で塗られています。 !\[\](https://img.atcoder.jp/abc355/4e83a6e54750f138ecada66dd93b2b67.png)