You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小蔡是一名树联网维护员。

具体地说，树联网的结构可以看作一颗树，用户就是树上的节点，边则是通信管道，每个通信管道都有一个脆弱值。

有一天，闲来无事的树联网用户们在所有通信管道中展开了一场大战，这使通信管道受到了损伤，每条通信管道受到的损伤值相当于通信管道两边用户数量之差乘以通信管道的脆弱值。

小蔡想知道，在这场大战过后，所有通信管道的损伤值之和是多少。

Input

第一行是一个整数$n$，表示树联网上一共有$n$个用户。

接下来$n$行，每行包含三个整数$a_i$，$b_i$和$c_i$，表示$a_i$和$b_i$节点之间有一条脆弱值为$c_i$的通信管道。

保证数据一定会组成一棵树。

Output

输出一个整数，表示所有通信管道的损伤值之和。

Examples

【样例 1 输入】

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

【样例 1 输出】

51

【样例 2 输入】

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

【样例 2 输出】

92

【样例 3 输入】

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

【样例 3 输出】

176

对于$100\%$的数据： $1 \leq c_i \leq 10^6$