描述

在 W 星球上有 $n$ 个国家（编号 $1$ 到 $n$），它们通过 $n-1$ 条双向道路连接成一棵树。每条道路连接两个国家 $a_i$ 和 $b_i$，长度为 $c_i$。修建该道路的费用定义为：$c_i \times \left| \text{删除这条边后，一侧连通块的国家数量} - \text{另一侧连通块的国家数量} \right|$。求所有道路的总修建费用。

输入输出格式

输入

第一行一个整数 $n$，表示国家数量。接下来 $n-1$ 行，每行三个整数 $a_i, b_i, c_i$，表示一条连接 $a_i$ 与 $b_i$、长度为 $c_i$ 的双向道路。

输出

一个整数，表示总费用。

样例

6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1

20

限制

• $2 \leq n \leq 10^6$
• $1 \leq a_i, b_i \leq n$，保证构成一棵树
• $0 \leq c_i \leq 10^6$
• 时间限制：2 秒；空间限制：512 MB