[Noi2011]道路修建

在 W 星球上有 $n$ 个国家。为了发展各自国家的经济，各国决定在国家之间修建双向道路，使所有国家互相连通。但是，每个国家的国王都很吝啬，他们只愿意修建恰好 $n-1$ 条双向道路。

由于修建的道路数量恰好为 $n-1$ ，且所有国家互相连通，因此建成的道路构成一棵树。对于每一条道路，若删除该道路，整棵树将分成两个连通块。设这两个连通块包含的国家数分别为 $x$ 和 $y$ ，该道路的长度为 $c$ ，则修建该道路的费用为 $c\times |x-y|$ 。修建所有道路的总费用为每条道路费用之和。

由于国家数量十分庞大，道路的建造方案有很多种，同时每种方案的修建费用都难以用人工计算，国王们决定设计一个软件，对于给定的道路建造方案，计算修建所有道路所需的总费用。请你帮助国王们完成这个任务。

输入格式

第一行包含一个整数 $n$ ，表示 W 星球上的国家数量。国家编号为 $1$ 到 $n$ 。

接下来 $n-1$ 行描述道路的建设情况。第 $i$ 行包含三个整数 $a_i$ 、 $b_i$ 和 $c_i$ ，表示第 $i$ 条双向道路连接国家 $a_i$ 与国家 $b_i$ ，其长度为 $c_i$ 。

输出格式

输出一个整数，表示修建所有道路所需的总费用。

样例输入

样例输出

数据范围

$1\le n\le 10^6$ ；
$1\le a_i,b_i\le n$ ；
$0\le c_i\le 10^6$ 。

来源与许可

本题为 NOI 2011 试题「道路修建」，题面与测试数据整理自 BZOJ。

样例 1

输入