注意

この問題の実行時間制限は $3$ 秒です。

問題文

$N$ 頂点からなる木があります。$i\ (1 \le i \le N-1)$ 本目の辺は頂点 $A_i$ と頂点 $B_i$ を双方向に結び、重みは $C_i$ です。

$1 \le i,j \le N$ かつ $i \neq j$ を満たす整数組 $(i,j)$ は $N(N-1)$ 通りありますが、それらのうち以下の条件を満たすものはいくつありますか？

• 頂点 $i$ から頂点 $j$ まで最短経路に沿って移動する過程において、通過した辺の重みのビットごとの XOR（排他的論理和）は常に $1$ 以上である。

入力

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$

• 入力はすべて整数
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \lt B_i \le N$
• $0 \le C_i \lt 2^{30}$
• 与えられるグラフは木

出力

答えを出力し、最後に改行してください。

サンプル

4
2 3 2
2 4 1
1 4 3

10

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

8

20
18 20 15
17 18 6
1 14 13
6 18 13
11 16 11
2 19 13
7 15 5
10 14 12
5 8 12
7 9 15
3 10 2
12 14 4
2 15 3
3 17 6
3 4 0
10 11 2
2 3 7
2 13 3
3 8 11

305