题目描述

给出一个有 $n−1$ 条边的树，求树上每两点之间最短路的最大权值边的和。

$ \displaystyle\ \sum_{i=1}^{n-1}\ \sum_{j=i+1}^n f(i,j) $ 其中 $f_{i,j}$ 为 $i\to j$ 所经过路径上边权的最大值。

输入格式

第一行输入一个整数 $n$

接下来 $n-1$ 行每行三个整数 $u,v,w$

输出格式

输出一个整数代表答案

3
1 2 10
2 3 20

50

5
1 2 1
2 3 2
4 2 5
3 5 14

76

提示

• $2\ \leq\ n\ \leq\ 10^5$
• $1\ \leq\ u_i,\ v_i\ \leq\ n$
• $1\ \leq\ w_i\ \leq\ 10^7$