### 问题描述 在遥远的星际，基德来到了一个神秘的星球，这个星球上有 $N$ 个城市，编号为 $1,2,\ldots,N$。星球上的每两个城市之间都有一条路径，路径的总数是 $N-1$ 条。第 $i$ 条路径 ($1 \leq i \leq N-1$) 连接了城市 $u_i$ 和城市 $v_i$，路径的长度为 $w_i$。 基德需要从一个城市出发，前往另一个城市。每个城市之间的最短路径都是唯一的。我们定义 $f(u,v)$ 为从城市 $u$ 到城市 $v$ 的最短路径中，路径长度最大的那一条。 基德在探险过程中，需要前往每一对城市，他需要知道所有的 $f(i,j)$ 的总和，其中 $1 \leq i < j \leq N$。 你能帮助基德解决这个问题吗？ ### 输入格式 输入的第一行包含一个整数 $N$，表示城市的数量。 接下来的 $N-1$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$，表示城市 $u_i$ 和城市 $v_i$ 之间有一条路径，长度为 $w_i$。 满足 $1 \leq N \leq 10^5$， $1 \leq u_i, v_i \leq N$，$u_i \neq v_i$， $1 \leq w_i \leq 10^9$。 ### 输出格式 输出一个整数，表示所有的 $f(i,j)$ 的总和。 ### 样例输入 ```plaintext 5 1 2 5 1 3 3 2 4 2 2 5 1 ``` ### 样例输出 ```plaintext 38 ```