汽车人变形
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

第 i 个区域有 a_i 个 homo，连接两个区域的道路上也会有 w 个 homo。

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

输入描述:

第一行一个正整数 。

第二行 n 个正整数 ，表示区域 i 上的 homo 数量。

接下来 n - 1 行，每一行包含三个正整数 ，表示  两区域之间有一条 homo 人数为 w 的道路连接。

输出描述:

输出一个正整数，表示车车能创到的最多 homo 数量。
示例1

输入

复制 
6
1 1 4 5 1 4
1 3 0
1 2 0
4 5 0
3 4 0
6 3 1

输出

复制 
15