E. Piza Removes Nothing
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Piza 扔给了你一颗树（ $$$n$$$ 个点 $$$n - 1$$$ 条边的无向联通图），并且给树上的每条边标上了一个权值（可能有负值），现在他想知道有多少条 $$$u$$$ 到 $$$v$$$ $$$(1 \le u, v \le n, u \ne v)$$$ 的最短路满足两点的路径上的边权和是正数。

Input

输入第一行包含一个正整数 $$$n$$$ $$$(2\le{n}\le{2\times{10^5}})$$$ ，代表树的节点个数。

随后 $$$n-1$$$ 行，每行包含三个整数 $$$u,v,w$$$ $$$(1\le{u,v}\le{n},\lvert w \rvert \le{10^9},u\neq{v})$$$ ，代表 $$$u,v$$$ 直接存在一条边权为 $$$w$$$ 的边。

Output

输出一个整数代表权值和为正的路径数。

Example
Input
5
1 2 -3
2 3 4
2 4 1
4 5 6
Output
8