4475: 旅行
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：12
通过：7
题目描述
给定一个 n 个节点的树，节点编号为 1∼n。
请你从中选择一个简单路径（不能包含重复节点或重复的边），并沿所选路径来一场旅行，更具体的说，就是从所选路径的一个端点沿路径前往另一个端点。
注意，所选简单路径可以只由一个节点组成。
旅行需要花费能量。
初始时，你的能量为 0。
在旅行过程中：
- 每经过一个节点（包括起点和终点），就可以得到该节点的能量，其中节点 i 包含的能量为 wi。
- 每经过一条边 (u,v)，就需要消耗一定的能量 c。
你设计的旅行路线应满足：
- 在经过任何一条边之前，你的现有能量都不能少于该边所需消耗的能量（否则，将无法顺利通过该边）。
- 在满足条件 1 的前提下，旅行结束时，剩余的能量尽可能大。
请计算并输出剩余能量的最大可能值。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 w1,w2,…,wn。
接下来 n−1 行，每行包含三个整数 u,v,c，表示存在一条边 (u,v)，经过它所需的能量为 c。
保证给定图是一棵树。
输出格式
一个整数，表示剩余能量的最大可能值。
输入样例 复制
3
1 3 3
1 2 2
1 3 2输出样例 复制
3数据范围与提示
前 3 个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤3×105，0≤wi≤109，1≤u,v≤n，u≠v，1≤c≤109。
所有测试点满足 1≤n≤3×105，0≤wi≤109，1≤u,v≤n，u≠v，1≤c≤109。
输入样例2：
5 6 3 2 5 0 1 2 10 2 3 3 2 4 1 1 5 1
输出样例2：
7