公平坚果要去树国旅行,那里有$$$n$$$城市。这个国家的大部分土地被森林覆盖。此外,当地的道路系统形成一棵树(无环的连通图)。 Nut 想在 $$$u$$$ 城市租一辆车,并通过一条简单的路径前往 $$$v$$$ 城市。他还没有确定道路,所以是时候去做了。请注意,所选路径只能包含一个顶点。
每个城市都有加油站。由于奇怪的法律,Nut 在第 $$$i$$$ 个城市只能购买 $$$w_i$$$ 升汽油。我们可以假设,他有无限的钱。每条路都有长度,当坚果驶过这条路时,汽油量就会随着长度的增加而减少。当然,努特不能选择一条道路,因为道路是由道路组成的,他在那里耗尽了汽油。他可以在每个访问过的城市购买汽油,即使是第一个和最后一个。
他还想找到路径尽头可以拥有的最大汽油量。帮助他:数一数。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — 城市数量。
第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \leq w_{i} \leq 10^9$$$) — Nut 在城市中可以购买的最大汽油量。
接下来的 $$$n - 1$$$ 行描述道路并包含三个整数 $$$u$$$、$$$v$$$、$$$c$$$ ($$$1 \leq u, v \leq n$$$, $$$1 \leq c \leq 10^9$$$, $$$u \ne v$$$),其中 $$$u$$$ 和$$$v$$$ — 由这条道路连接的城市,$$$c$$$ — 其长度。
保证道路连通图是一棵树。
输出
打印一个数字——他在路径尽头可以拥有的最大汽油量。
示例
输入 #1
3 1 3 3 1 2 2 1 3 2
输出 #1
3
输入 #2
5 6 3 2 5 0 1 2 10 2 3 3 2 4 1 1 5 1
输出 #2
7
注意
第一个示例中的最佳方式是 $$$2 \to 1 \to 3$$$。
第二个示例中的最佳方式是 $$$2 \to 4$$$。