AT_abc214_d [ABC214D] Sum of Maximum Weights

有一棵包含 $N$ 个顶点的树，顶点编号为 $1, 2, \dots, 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)$ 的值。

输入以如下格式从标准输入读入。 > $N$ > $u_1$ $v_1$ $w_1$ > $\vdots$ > $u_{N-1}$ $v_{N-1}$ $w_{N-1}$

请输出答案。

## 限制条件 - $2 \leq N \leq 10^5$ - $1 \leq u_i, v_i \leq N$ - $1 \leq w_i \leq 10^7$ - 给定的图是一棵树。 - 所有输入均为整数。 ## 样例解释 1 $f(1, 2) = 10,\ f(2, 3) = 20,\ f(1, 3) = 20$，因此它们的和为 $50$，输出 $50$。 由 ChatGPT 4.1 翻译