说明

在 ICPC 公园里，有一棵巨大的树，一群松鼠在上面筑巢。

松鼠的巢穴由 $N$ 个房间（编号为 $1, 2, \ldots, N$）和 $N - 1$ 条双向道路（编号为 $1, 2, \ldots, N - 1$）组成，这些道路连接着各个房间。保证任意两个房间都可以通过这些道路相互到达。

房间 $1$ 是松鼠群的集合地点，而其他房间则用作卧室。每个房间 $i$ 住着 $a_i$ 只松鼠，其中 $a_1 = 0$。

现在，松鼠们正试图从它们的卧室出发，沿着道路前往房间 $1$ 进行晨会。然而，由于昨晚的一场严重风暴，每条道路都变得脆弱不堪，第 $i$ 条道路在坍塌前最多只能允许 $c_i$ 只松鼠通过。

作为一名动物爱好者，你的任务是选择一条道路进行加固，以使得能够到达房间 $1$ 的松鼠数量最大化。被加固的道路无论有多少松鼠通过都不会坍塌。

输入格式

输入包含一个单独的测试用例，格式如下。

$$\begin{aligned} &N \\ &a_1 \ a_2 \ \ldots \ a_N \\ &u_1 \ v_1 \ c_1 \\ &u_2 \ v_2 \ c_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \ c_{N-1} \end{aligned}$$

第一行包含一个整数 $N$，其值在 $2$ 到 $200,000$ 之间（含端点）。

第二行包含 $N$ 个非负整数 $a_1, a_2, \ldots, a_N$。整数 $a_i$ 表示居住在房间 $i$ 的松鼠数量，其中 $a_1 = 0$，且对于 $i = 2, 3, \ldots, N$，有 $0 \leq a_i \leq 10^9$。

接下来的 $N - 1$ 行，每行包含三个整数 $u_i$, $v_i$ 和 $c_i$（$1 \leq u_i, v_i \leq N$，$0 \leq c_i \leq 10^9$）。$u_i$ 和 $v_i$ 表示第 $i$ 条道路的两个端点，$c_i$ 表示其耐久度。

保证给定的图是一棵树。

输出格式

输出能够到达房间 $1$ 的松鼠的最大数量。

8
0 11 13 14 17 19 15 12
1 2 5
2 3 2
3 4 3
1 5 2
5 6 5
1 7 4
7 8 3

31

提示

翻译由 DeepSeek V3.2 完成