题目描述

小蓝居住的国家有 $n$ 座城市，城市与城市之间由 $n-1$ 条公路连接，而且任意两个城市都可以通过公路互相到达。

这个国家的公路由几个公司共同修建，如果小蓝希望通过某条公路，就必须持有修建这条公路的公司的通行证，但只要申请一次通行证，就可以在每一条这个公司修建的公路上通行。

小蓝经常要在不同城市之间旅行，每次他要从一个城市到另一个不同的城市，都需要根据需要通过的公路申请相应的通行证。具体来说，如果小蓝的路线经过了一条或者更多条 A 公司修建的公路，小蓝就需要申请一次 A 公司的通行证。

现在小蓝希望知道，对于这 $n \times (n-1)$ 种不同的情况，他需要申请通行证的次数总共是多少。

输入格式

输入的第一行包含一个正整数 $n$。

接下来 $n-1$ 行，每行包含三个正整数 $u_i, v_i, w_i$，相邻整数之间使用一个空格分隔，表示城市 $u_i$ 和城市 $v_i$ 之间有一条由公司 $w_i$ 修建的公路。

输出格式

输出一行包含一个整数表示答案。

4
1 2 1
1 3 1
1 4 2

16

提示

【样例说明】

下表给出了每种情况需要申请的通行证数量，总和为 16。

【评测用例规模与约定】

对于 30% 的评测用例，$1 \leq n \leq 300$；

对于另外 20% 的评测用例，$u_i = i$，$v_i = i + 1$；

对于另外 20% 的评测用例，$u_i = 1$，$v_i = i + 1$；

对于 80% 的评测用例，$1 \leq n \leq 50000$；

对于所有评测用例，$1 \leq w_i, u_i, v_i \leq n \leq 500000$。