题目描述

我们有一棵 $N$ 个顶点的树，顶点编号为 $1, 2, \ldots, N$。
第 $i$ 条边（$1 \leq i \leq N - 1$）连接顶点 $u_i$ 和顶点 $v_i$，边的权重为 $w_i$。

对于不同的顶点 $u$ 和 $v$，令 $f(u, v)$ 表示从顶点 $u$ 到顶点 $v$ 的最短路径中包含的边的最大权重。

求 $\\displaystyle \\sum_{i = 1}^{N - 1} \\sum_{j = i + 1}^N f(i, j)$。

约束条件

• $2 \leq N \leq 10^5$
• $1 \leq u_i, v_i \leq N$
• $1 \leq w_i \leq 10^7$
• 给定的图是一棵树。
• 输入中的所有值均为整数。

输入

从标准输入中按以下格式给出输入：

$N$ $u_1$ $v_1$ $w_1$ $\\vdots$ $u_{N - 1}$ $v_{N - 1}$ $w_{N - 1}$

输出

打印答案。

示例输入 1

3
1 2 10
2 3 20

示例输出 1

50

我们有 $f(1, 2) = 10$，$f(2, 3) = 20$，$f(1, 3) = 20$，因此我们应该打印它们的和，即 $50$。

示例输入 2

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

示例输出 2

76