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

This is the hard version of the problem. The difference between the versions is that in this version, the path may end in any 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 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 two traversals of the same corridor, its vault becomes too fragile, and it is impossible to use this corridor a third time. Therefore, Henry may 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 instead 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 there. The lamp charge must never become negative at any moment.

Henry must visit all caves and collect all artifacts. After that, he can activate a portal in any cave and leave the dungeon, so he does not need to return to the entrance.

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

Input

The first line 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

Print one integer — the minimum initial lamp charge with which Henry can visit all caves without the lamp charge ever becoming negative.

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