P2986 [USACO10MAR] Great Cow Gathering G

题目描述

给出有 $N$ 个点权点 $N-1$ 条带权边的一颗无根树。

第 $i$ 条边，连接点$A_i$ 和 $B_i$，长度为 $L_i$ 。

第 $i$ 个点住着 $C_i$ 只牛。

现要选其中某个点作为集会点（所有奶牛都要走到集会点集中），使得奶牛们所走路程和最小。

输入格式

第一行一个整数 $N(1\leq N\leq 10^5)$ 。

下来 $N$ 个整数 $C_i$。

下来 $N-1$ 行，每行 $3$ 个整数：$A_i \ B_i \ L_i$ $(1\leq A_i\leq B_i\leq N$，$0 \leq C_i,L_i \leq 10^3)$。

输出格式

一行一个整数，表示奶牛们所走路程和最小值。

输入

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

输出

15