#ZF1093. 汽车人变形

汽车人变形

Description

车车喜欢创人,一天车车创完 114514114514 个城市的人后,来到了一个全是 homo 的新城市,这个城市有 nn 个区域,由 n1n-1 条道路连接,各区域之间都可以互相到达,你可以将整个城市看成一棵树。

ii 个区域有 aia_i 个 homo,连接两个区域的道路上也会有 ww 个 homo。

车车将会选择一个区域空降,并选择一条路径创到底,车车不会回头,现在请你找出一条路径使得车车创到的 homo 总人数最多。

Format

Input

第一行一个正整数 n(1n5×103)n(1 \leqslant n \leqslant 5 \times 10^3)

第二行 nn 个整数 $a_1,a_2, \cdots, a_n(0 \leqslant a_i \leqslant 10^9)$,表示区域 ii 上的 homo 数量。

接下来 n1n - 1 行,每一行包含三个整数 $a,b,w(1 \leqslant a,b \leqslant n, 0 \leqslant w \leqslant 10^9)$,表示 a,ba, b 两区域之间有一条 homo 人数为 ww 的道路连接。

Output

输出一个整数,表示车车能创到的最多 homo 数量。

Samples

6
1 1 4 5 1 4
1 3 0
1 2 0
4 5 0
3 4 0
6 3 1
15

Limitation

2s, 1024KiB for each test case.