辺の重みの最大値を \(W=10\) とします．グラフ \(G\) の部分グラフであって，\(G\) の辺のうち重みが \(k\) 以下であるものからなる（重みなし）グラフを \(G_k (0\leq k\leq W)\) とします．グラフ \(H\) の連結成分数を \(c(H)\) とするとき，グラフ \(G\) の MST （最小全域木）に含まれる辺の重みの和は \(\displaystyle \sum_{k=0}^{W-1}\left( c(G_k)-1\right)\) と等しくなります．

（証明）
（方針 1） \(G\) の MST に含まれる辺のうち，重みが \(k\) 以下 であるものは \(N-c(G_k)\) 個です（クラスカル法のアルゴリズムより，重みが小さい辺を MST に追加できるだけ追加するべきであるため）．したがって，重みが ちょうど \(k\) であるものは \(\left(N-c(G_k)\right)-\left(N-c(G_{k-1})\right)=c(G_{k-1})-c(G_k)\) 個あり，グラフ \(G\) の MST に含まれる辺の重みの和は \(\displaystyle \sum_{k=1}^{W}k\left(c(G_{k-1})-c(G_k)\right)=\displaystyle \sum_{k=0}^{W-1}\left( c(G_k)\right)-W\cdot c(G_W)=\displaystyle \sum_{k=0}^{W-1}\left( c(G_k)-1\right)\) です．

（方針 2）\(G\) の MST に含まれる辺のうち，重みが \(k\) 以上のものは \(c(G_{k-1})-1\) 個です（\(G_{k-1}\) を連結にするためには \(c(G_{k-1})-1\) 個の辺を追加する必要があるため）．したがって，主客転倒によりグラフ \(G\) の MST に含まれる辺の重みの和は \(\displaystyle\sum_{k=1}^{W}\left(c(G_{k-1})-1\right)=\displaystyle \sum_{k=0}^{W-1}\left(c(G_k)-1\right)\) です（証明終）

各 \(k(0\leq k\lt W)\) に対して， \(G_k\) の連結成分数を Union-Find で管理することによってこの問題を計算量 \(O(W(N+Q)\alpha(N))\) で解くことができます．（計算量は \(O((WN+Q)\alpha(N))\) に落とすことが可能です．）

以下の実装例では次のような工夫をしています．

• \(G\) には最初から \(N-1\) 個の重み \(10\) の辺 \(\{1,2\},\{1,3\},\dots,\{1,N\}\) が貼られており，\(N-1+Q\) 個の辺追加クエリがあるとみなす．
• 答えを直接管理する．最初の時点では \(c(G_{k})=N(0\leq k\lt 10)\) であるため \(\mathrm{ans}=10N-10\) である．各クエリに対して，連結成分数が減るごとに答えを更新する．

from atcoder.dsu import DSU

N, Q = map(int, input().split())
uf = [DSU(N + 1) for i in range(10)]
ans = 10 * N - 10
for i in range(N - 1 + Q):
    a, b, c = map(int, input().split())
    for j in range(c, 10):
        if not uf[j].same(a, b):
            ans -= 1
            uf[j].merge(a, b)
    if i >= N - 1:
        print(ans)