题目描述

给你一个有 $n$ 个结点的二叉树，根结点为 1 。

二叉树上每个节点有多干个金币（也可能没有金币） ，整棵树上一共有 $n$ 枚金币。可以沿着树枝移动金币，每次只能在相邻节点之间移动 $1$ 枚金币。 金币的移动可以是从父结点到子结点，或者从子结点移动到父结点。

希望通过若干次的移动，使得最终每个节点都有 1 枚金币，求最少移动次数。

输入格式

第一行一个整数 $n$，代表二叉树上的节点数。

接下来有 $n$ 行，每一行包含 3 个数字，第 $i$ 行的 $3$ 个数字为 $l_i , r_i, w_i$，表示节点 $i$ 节点的左热为为 $l_i$，右儿子为 $w_i$，节点 $i$ 上有 $w_i$ 个金币。当节点 $i$ 没有左儿子的时候，$l_i$ 为 0， 当 $i$ 没有右儿子的时候 $r_i$ 为 $0$。

数据规模

$1 \lt n \le 10^5$

$1 \le l_i, r_i \le n$

$\sum w_i == n$

输出格式

一个整数，代表最小的移动次数。

样例

5
2 4 0
0 0 0
0 5 0
0 3 3
0 0 2

4