有一棵拥有 $n$ 个顶点和 $n - 1$ 条无向边的树。每条边可能具有不同的长度。

我们定义 $dis(u, v)$ 为从顶点 $u$ 到顶点 $v$ 的路径长度之和。

现在，你需要计算满足 $dis(u, v)$ 为奇数的所有无序顶点对 $(u, v)$ 的数量。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示顶点的数量。

接下来的 $n-1$ 行，每行包含三个整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9$)，表示一条连接顶点 $u_i$ 和 $v_i$ 且长度为 $w_i$ 的边。

输出格式

输出一个整数，表示你的答案。

样例

输入样例 1

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

输出样例 1

6

输入样例 2

10
5 7 1
10 3 1
4 2 5
5 1 7
4 9 10
1 4 5
8 7 6
5 10 5
6 9 4

输出样例 2

25

说明

在第一个样例中，这 $6$ 个无序顶点对分别为 $(1, 2)$、$(1, 3)$、$(1, 5)$、$(2, 4)$、$(3, 4)$、$(4, 5)$。