CF1083A.The Fair Nut and the Best Path

The Fair Nut is going to travel to the Tree Country, in which there are $n$ cities. Most of the land of this country is covered by forest. Furthermore, the local road system forms a tree (connected graph without cycles). Nut wants to rent a car in the city $u$ and go by a simple path to city $v$. He hasn't determined the path, so it's time to do it. Note that chosen path can consist of only one vertex.

A filling station is located in every city. Because of strange law, Nut can buy only $w_i$ liters of gasoline in the $i$-th city. We can assume, that he has infinite money. Each road has a length, and as soon as Nut drives through this road, the amount of gasoline decreases by length. Of course, Nut can't choose a path, which consists of roads, where he runs out of gasoline. He can buy gasoline in every visited city, even in the first and the last.

He also wants to find the maximum amount of gasoline that he can have at the end of the path. Help him: count it.

公平的坚果将前往树之国旅行，该国有 $n$ 座城市。这个国家的大部分土地被森林覆盖。此外，当地的公路系统构成一棵树（即无环的连通图）。坚果希望在城市 $u$ 租一辆车，并沿一条简单路径前往城市 $v$。他尚未确定具体路径，现在是时候决定了。注意：所选路径可以仅包含一个顶点。

每座城市都设有一座加油站。由于一项奇特的法律，坚果在第 $i$ 座城市最多只能购买 $w_i$ 升汽油。我们可以假设他拥有无限的资金。每条道路都有一个长度，一旦坚果驶过该道路，其汽油量就会减少该长度值。显然，坚果不能选择一条会导致他在途中耗尽汽油的路径。他可以在访问到的每一座城市购买汽油，包括起点和终点城市。

他还希望找出在路径终点时所能拥有的最大汽油量。请帮助他计算该值。

The first line contains a single integer $n$ ($1 \leq n \leq 3 \cdot 10^5$) — the number of cities.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($0 \leq w_{i} \leq 10^9$) — the maximum amounts of liters of gasoline that Nut can buy in cities.

Each of the next $n - 1$ lines describes road and contains three integers $u$, $v$, $c$ ($1 \leq u, v \leq n$, $1 \leq c \leq 10^9$, $u \ne v$), where $u$ and $v$ — cities that are connected by this road and $c$ — its length.

It is guaranteed that graph of road connectivity is a tree.

第一行包含一个整数 $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$ 是该道路的长度。

保证道路连通性构成的图是一棵树。

Print one number — the maximum amount of gasoline that he can have at the end of the path.

输出一个数字——他在路径终点所能拥有的汽油最大量。

The optimal way in the first example is $2 \to 1 \to 3$.

The optimal way in the second example is $2 \to 4$.

第一个样例的最优路径是 $2 \to 1 \to 3$。

第二个样例的最优路径是 $2 \to 4$。