F1. Expedition (easy version)
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The difference between the versions is that in this version you need to finish the path in the starting cave.

Henry went on an expedition into a network of caves in search of ancient artifacts. The entrance to the caves is at vertex $$$1$$$, and the corridors between the caves form a tree.

Henry lights his way with a magic lamp. To pass through the $$$i$$$-th corridor, the lamp spends $$$w_i$$$ units of charge each time it is traversed.

However, the cave corridors are extremely unstable. After being traversed twice, a corridor becomes too fragile, and it is impossible to use it a third time. Therefore, Henry can traverse each corridor at most twice, regardless of the direction of movement.

There is an artifact in every cave. On the first visit to vertex $$$v$$$, the artifact changes the lamp charge by $$$a_v$$$ units: some artifacts restore charge (those with $$$a_v \gt 0$$$), while others are cursed and, on the contrary, take it away ($$$a_v \lt 0$$$). Visiting the cave again has no effect on the lamp charge.

At the beginning of the expedition, Henry is in cave $$$1$$$ and immediately activates the artifact located there. The lamp charge must never become negative at any moment.

Henry must visit all caves and collect all artifacts. After that, he must return to cave $$$1$$$ and leave the dungeon.

Determine the minimum initial lamp charge with which Henry can complete the expedition.

Input

The first line of the input contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the number of caves.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — the changes in lamp charge after the first visit to the corresponding caves. Note that each corridor can be traversed at most twice, regardless of direction.

The next $$$n - 1$$$ lines contain three integers each: $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ $$$(1 \le u_i, v_i \le n,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$$$ — the endpoints of the $$$i$$$-th corridor and the amount of charge required to traverse it.

It is guaranteed that the corridors form a tree.

Output

In a single line, print one integer — the minimum initial lamp charge with which Henry can visit all caves without ever letting the lamp charge become negative.

Examples
Input
5
1 10 -2 6 7
1 2 10
1 3 2
3 4 1
3 5 7
Output
18
Input
4
2 -90 15 30
1 2 4
2 3 5
1 4 10
Output
87