样例下载

问题描述

奶牛 Bessie 准备在狂欢节上燃放她最新制作的烟花树。

烟花树可以看作一棵有根树，树中有 $n$ 个节点，从 $1$ 到 $n$ 编号，其中 $1$ 号节点为根，叶子节点是烟花节点，其余节点是中继节点。所有节点由导火索连接起来。火花通过每条导火索需要一定时间，不同的导火索燃烧所需时间不一定相同。Bessie 将点燃 $1$ 号节点，火花就会从 $1$ 号节点开始沿导火索扩散，直至到达并点燃所有烟花节点。Bessie 希望所有烟花节点同时点燃，为此她可以延长某些导火索。具体的，她可以花费 $x(x>0)$ 的代价使火花通过某条导火索的时间增加 $x$。

Bessie 想知道，要想使所有烟花节点同时点燃，她需要花费的最小代价是多少。

Farmer John 提供的简洁版题意：有一棵带权有根树，你可以花费 $x(x>0)$ 的代价使某条边边权增加 $x$。求使所有叶节点到根的带权距离相等的最小代价。

输入格式

输入的第一行包含一个整数 $n$，代表节点的个数。

之后有 $n-1$ 行，每行 $3$ 个整数 $u,v,w$，表示 $u,v$ 之间有一条导火索，其燃烧所需的时间为 $w$。

输出格式

输出共 $1$ 行，包含一个正整数，表示需要花费的最小代价。

输入输出样例

输入

3
1 2 1
1 3 3

输出

2

数据规模与约定

对于 $20\%$ 的数据，$n\le 100$，$1\le w\le 100$；

对于 $50\%$ 的数据，$n\le 1000$，$1\le w\le 100$；

对于另外 $10\%$ 的数据，保证只有一个烟花节点；

对于 $100\%$ 的数据，$n\le500000$，$1\le w\le 10^6$。