Gold Distribution Balancing

In the kingdom of Numiland, Rey is given the task of balancing the gold distribution among its cities. The kingdom consists of n cities connected by m bidirectional roads. Each city has an initial amount of gold. Although Rey possesses a magical tool that can transfer gold between two directly connected cities (only once per road), his objective is to achieve the minimum possible absolute difference in gold between any two directly connected cities after performing a series of transfers.

You are provided with the number of test cases. For each test case, you are given:

• An integer n representing the number of cities.
• An integer m representing the number of roads.
• A list of n integers representing the initial amount of gold in each city.
• m roads where each road is represented by three integers u, v, and l. Although l denotes the road's length, the transfers are only allowed along the road and the length does not affect the calculation.

Your task is to compute, for each test case, the minimum possible absolute difference in gold between any two directly connected cities. Mathematically, if the gold in city u is g_u and in city v is g_v, you need to find:

$$\min \; |g_u - g_v|$$

over all roads connecting city u and city v, taking into account that transfers might be performed optimally. Note that if all cities initially have the same amount of gold, the answer would be 0.

inputFormat

The input is read from standard input (stdin) with the following format:

t
n m
gold[0] gold[1] ... gold[n-1]
u1 v1 l1
u2 v2 l2
... (m lines)
... (repeat for each test case)

Where:

• t: the number of test cases.
• n: number of cities.
• m: number of roads.
• Next line contains n integers representing the gold in each city.
• Each of the next m lines contains three integers: u, v, and l.

outputFormat

For each test case, output an integer on a new line representing the minimum possible absolute difference in gold between any two directly connected cities after optimal transfers.

## sample

2
4 4
10 30 20 40
1 2 1
2 3 1
3 4 1
4 1 1
3 2
15 25 35
1 2 10
2 3 10

10
10

</p>