Description

对于完全图 G，若有且仅有一棵最小生成树为 T，则称完全图 G 是树 T 扩展出的。

给你一棵树 T，找出 T 能扩展出的边权和最小的完全图 G。

注意： T 和 G 中的边权均取正整数。

Input

第一行包含一个整数 N 表示树 T 的点数；

接下来 N−1 行每行三个整数 $S_i,T_i,D_i$；描述一条边 $(S_i, T_i)$ 权值为 $D_i$；

保证输入数据构成一棵树。

Output

输出仅一个数，表示最小的完全图 G 的边权和。

Samples

123 500

623

Limitation

样例说明

添加 D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。

数据范围：

对于 20% 的数据，N≤10；

对于 50% 的数据，N≤1000；

对于 100% 的数据，N≤$10^5$,1≤$D_i$≤$10^5$ 。