It is a well known fact that Sam is an incredibly talented programmer. However, his teacher Bruce is beginning to have doubts.

To test his suspicions, Bruce drops Sam off in a faraway island of $N$ connected islands, joined by $N-1$ bidirectional bridges. However, the bridges are brittle, so bridge $i$ can only be traversed a maximum of $t_i$ times. Moreover, the $i^{\text{th}}$ of the $N$ islands houses a treasure chest of value $v_i$.

Right before Bruce leaves to teach Sam's class without him, he tells Sam that he has one chance to tell him the maximum value of treasure chests he can obtain. If he fails to do so, Bruce will leave Sam stranded on the island forever. However, Sam is unable to solve this problem. He passes it on to Daniel, who passes it on to you to solve!

Give that Sam starts at island $1$ and can end at any island, help Daniel find the right answer for Sam!

Constraints

For all subtasks:

$1\le v_i,t_i\le {10}^9$

$1\le A_i,B_i\le N$

Subtask 1 [20%]

$1\le N\le 8$

Subtask 2 [30%]

$1\le N\le 2\times {10}^3$

Subtask 3 [50%]

$1\le N\le 2\times {10}^5$

Input Specification

The first line of input will contain the integer $N$, the number of islands.

The second line of input will contain $N$ positive integers $v_i$.

The next $N-1$ lines will contain $A_i$, $B_i$, and $t_i$, representing a bidirectional edge between $A_i$ and $B_i$ that can be traversed a maximum of $t_i$ times.

Output Specification

Output one integer representing the maximum amount of treasure Sam can gather. Please note that 64-bit integers may be required for full marks.

Sample Input 1

3
4 8 5
1 2 2
2 3 2

Sample Output 1

17

Explanation for Sample Output 1

Sam's optimal path is $1\to 2\to 3$, gathering $4+8+5=17$ units of treasure. Note that Sam is able to return to his starting position, but this is not required for this case.

Sample Input 2

5
8 10 4 9 1
1 2 1
1 3 2
2 4 1
2 5 1

Sample Output 2

31

Explanation for Sample Output 2

Sam's optimal path is $1\to 3\to 1\to 2\to 4$, gathering $8+4+0+10+9=31$ units of treasure. Note that since each treasure chest can only be retrieved once, returning to island $1$ doesn't grant additional treasure.