题目描述

一张计算机网络有 $n$ 台计算机和 $n-1$ 条连接，任意两台计算机之间都可以通过这些连接交换信息。

每条连接有一个传输速度。设 $d(a,b)$ 为计算机 $a$ 与 $b$ 之间路径上最慢连接的速度。请计算所有计算机点对之间传输速度的总和。

输入格式

第一行包含一个整数 $n$，表示计算机数量。计算机编号为 $1,2,\ldots,n$。

接下来 $n-1$ 行，每行包含三个整数 $a,b,x$，表示计算机 $a$ 与 $b$ 之间有一条传输速度为 $x$ 的连接。

输出格式

输出一个整数，表示所有点对的传输速度总和。

数据范围

• $1 \le n \le 2\cdot 10^5$
• $1 \le x \le 10^6$

样例

样例输入

4
1 2 5
2 3 1
2 4 2

样例输出

12

样例说明

有 $d(1,2)=5$，$d(1,3)=1$，$d(1,4)=2$，$d(2,3)=1$，$d(2,4)=2$，$d(3,4)=1$，总和为 $12$。