Problem Description

Penguin loves driving. One day he found some islands, and wanted to go on a tour.

These $n$ islands are connected by $n - 1$ undirected roads, the $i$-th road connects island $u_i$, $v_i$ take $w_i$ to pass. Any two islands can reach each other. The i-th island has a power value $p_i$. You can do the following operations at most once for each island:

1. Choose a road that connects to the island

2. Change the cost of the road $w$ to $max(0,w-p)$

The penguin will choose an island arbitrarily and follow the shortest path to another island. Since the penguin likes to travel long distances, he will choose the longest path from all possible options.But you don't want to make his journey too tiring. Can you reasonably allocate the power value of each island to make the penguin's travel as short as possible?

Input

The first line contains an integer $T(T \le 1000)$. Then $T$ test cases follow.

For each test case the first line contains one integer $n(1\le n\le 10^5)$.

Then a line with $n$ integers, $p_1, p_2, ..., p_n$ $(0 \le p_i \le 10 ^ 5) $ the power of the islands.

Then $n - 1$ lines, each line containing three integers $u_i$, $v_i$, $w_i$ $ (1 \le u_i, v_i \le n, 1 \le w_i \le 10^5)$ describing a road.

It is guaranteed that $\sum n <4\times10^5 $.

Output

For each test case, print a line with an integer, representing the shortest travel length.

1
9
3 2 1 1 2 2 4 4 3
5 3 5
4 2 1
6 4 1
2 1 1
3 2 2
9 2 4
7 5 3
8 4 4

3