描述

给定一棵以 1 为根的二叉树（节点编号为 1 到 n），每个节点有一个居民人口数 w。要求选择一个节点建立医院，使得所有居民到该医院的路径距离之和最小。树中相邻节点间距离为 1，路径长度即为两点间唯一简单路径上的边数。

输入输出格式

输入

第一行一个整数 n，表示节点总数（1 ≤ n ≤ 100）。 接下来 n 行，每行三个整数 w, u, v：

• w 表示该节点（编号即为当前行序号，从 1 开始）的居民人口数；
• u 表示左子节点编号（0 表示无左子）；
• v 表示右子节点编号（0 表示无右子）。

输出

一个整数，表示所有居民到最优医院位置的最小总距离和。

样例

5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0

81

限制

• 时间限制：1 秒
• 空间限制：256 MB
• 1 ≤ n ≤ 100
• 每个节点人口 w 满足 1 ≤ w ≤ 10⁵
• 左/右子节点编号 u, v 满足 0 ≤ u, v ≤ n，且非零时必为有效节点编号（1~n）