#1374. [L2-4]拜树年

食肉斯特是一只土拨鼠！

有 $n$ 只食肉斯特，他们居住的地方构成了一棵树。某一天，食肉斯特们不约而同地决定拜访其他人的住所。在拜访其他人住所的过程中，他们产生了一个问题：

如果所有人都从自己住所出发，拜访其他人的住所，每一次拜访都要从自己家出发，拜访完一处后就要回家，所有人拜访完所有住所所经过的边的和是多少。

你能帮食肉斯特们解决这个问题吗？

形式上来说，令 $dis(x,y)$ 表示 $x$ 点和 $y$ 点之间的最短路径包含的边权和，求

$$2\sum_{i=1}^n \sum_{j=1}^n dis(i,j)$$

树: 由 $n$ 个点 $n-1$ 条边形成的连通图。

第一行1个正整数 $n$ 。表示 $n$ 个点。

接下来 $n-1$ 行输入三个正整数 $u_i$ , $v_i$ , $w_i$ 表示每条边的起点，终点，边权。

输出一个正整数表示答案。

样例输入

4
1 2 1
1 3 2
2 4 4

样例输出

88

样例解释

对于样例2，每两个点之间的最短路径长度如下表格所示：

$\rm{ans}=2\times (0+1+2+5+1+0+3+4+2+3+0+7+5+4+7+0)=88$

对于 $100\%$ 的数据，满足 $1 \leq n\leq 2 \times 10^5$ ， $1 \leq w_i \leq 2\times 10^5$。