B 生成树（tree）

TIME:2S MEMORY:1024M

【问题描述】

​ 给定一棵树，有边权（可正可负）。构造一张新的带权完全图 $G$，其中 $(u,v)$ 之间的边边权为 $|dis(u,v)|$，其中 $dis(u,v)$ 指树上 $u,v$ 两点间唯一简单路径上的边权之和。

​ 求图 $G$ 的最小生成树中边权之和。

【输入格式】

​ 从文件 $\text{tree.in}$ 中读取数据。

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

​ 接下来 $n-1$ 行，每行三个整数 $u_i,v_i,w_i$，表示树上的一条边。

【输出格式】

​ 输出到文件 $\text{tree.out}$ 中。

​ 输出一行一个整数，表示 $G$ 的最小生成树边权之和。

【样例输入1】

5
3 4 -5
3 5 6
2 4 -8
1 5 6

【样例输出1】

13

【样例2】

​ 见选手目录下的 $tree/tree2.in$ 与 $tree/tree2.ans$。

【数据范围及约定】

​ 保证 $1\le n\le 2\times 10^5,1\le u_i,v_i\le n,-10^9\le w_i\le 10^9,n-1$ 条边形成一棵树。