“Triangoes” 是一种新型水果，呈三角形，吃起来像芒果。然而，世界上从来没有人见过“triangoes”，因为它们总是隐式地生长在树上，并隐藏在三角形中。形式化地说，“triango”树是一棵带权边的无环无向连通图（即树），而一个“triango”是指“triango”树上的一组三个顶点，使得这三个顶点两两之间的三条简单路径的长度满足三角形不等式；也就是说，它们构成一个三角形。

经过长途跋涉，Suzukaze 终于在他的房子里发现了一棵“triango”树。他需要你的帮助来计算这棵“triango”树上“triangoes”的数量。你能帮帮他吗？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示“triango”树上的顶点数量。“triango”树的顶点编号从 $1$ 到 $n$。

接下来的 $n-1$ 行，每行包含 3 个整数 $u, v, w$ ($1 \le u, v \le n, u \neq v, 1 \le w \le 10^5$)，表示有一条权重为 $w$ 的无向边连接顶点 $u$ 和顶点 $v$。

保证输入数据是一棵无环无向连通图。

输出格式

输出一个整数，表示“triango”树上“triangoes”的数量。

样例

样例输入 1

7
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
3 7 1

样例输出 1

8