B. Apple Tree
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There is a huge apple tree in your backyard. After years of growth, the tree is now full of apples. You know that the tree consists of $$$N$$$ nodes, and there are $$$a_i$$$ apples on the $$$i$$$-th node. You also know the length of each edge in the tree. You are planning to harvest the apples on the tree. To do that, you come up with a unique way of harvesting apples. Firstly, you select a set of nodes from which you are going to collect apples. Then you design a route that passes through all the nodes you selected and returns to the starting node (the route can start from any node in the tree). The score of a harvesting plan is defined as the total amount of harvested apples subtracting the total length of the route. Find the highest score among all harvesting plans.

Input

The first line consists of a single integer $$$N$$$, representing the number of nodes.

The second line consists of $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$, representing the number of apples on the nodes.

The following $$$N-1$$$ lines describe the tree. Each line consists of three integers, $$$u_i, v_i, l_i$$$, meaning that there is an edge of length $$$l_i$$$, connecting the $$$u_i$$$-th node and the $$$v_i$$$-th node.

  • $$$1 \leq N \leq 10^{6}$$$
  • $$$1 \leq u_i, v_i \leq N$$$
  • $$$1 \leq a_i, l_i \leq 10^{9}$$$
  • It is guaranteed that the input forms a tree
Output

Output one line containing an integer, representing the highest possible score.

Examples
Input
4
3 3 3 3
1 2 3
2 3 1
2 4 2
Output
4
Input
4
3 3 3 3
1 2 10
2 3 10
2 4 10
Output
3
Input
10
5 5 7 10 9 5 10 9 10 7
6 3 10
1 4 2
9 1 6
8 5 10
2 6 9
8 2 6
8 7 4
9 8 1
9 10 8
Output
19