問題文

$N$ 頂点 $N-1$ 辺の無向木があります。頂点は $1$ から $N$ までで、辺は $1$ から $N-1$ まででそれぞれ番号付けられており、$i$ 番目の辺は頂点 $u_i$ と $v_i$ を双方向に結んでいます。また、それぞれの辺には色がついています。色は全部で $K$ 色存在し、$i$ 番目の辺には色 $c_i$ が付いています。

この木のパス $(p,q)$ (ただし $p<q$) であって、パスに含まれる辺の色が ちょうど $2$ 種類 であるものの個数を求めてください。なお、パス $(p,q)$ に含まれる辺とは、頂点 $p$ から頂点 $q$ まで最短経路で向かう際に通過する辺の集合を指します。

入力

$N$ $K$
$u_1$ $v_1$ $c_1$
$⋮$
$u_{N-1}$ $v_{N-1}$ $c_{N-1}$

$1$ 行目では、木の頂点数 $N$ と色の種類数 $K$ が与えられます。

$2$ 行目以降 $N-1$ 行は、木の辺の情報が与えられます。$1+i$ 行目 $(1\le i\le N-1)$ は、$i$ 番目の辺が頂点 $u_i$ と頂点 $v_i$ を双方向に接続しており、辺の色が $c_i$ であることを表します。

制約

• 入力は全て整数で与えられる
• $1\le N\le 2\times {10}^5$
• $1\le K\le 2\times {10}^5$
• $1\le u_i,v_i\le N$ $(1\le i\le N-1)$
• $1\le c_i\le K$ $(1\le i\le N-1)$
• 与えられるグラフは木であることが保証される

出力

答えを $1$ 行で出力してください。

サンプル

5 5
1 2 3
1 3 1
2 4 5
3 5 1

3

8 149146
4 2 42027
2 5 83386
2 6 47328
3 6 37766
7 2 130178
7 1 9283
8 2 48943

12