Cycling

You want to cycle to a programming contest. The shortest route there may climb over mountain tops and drop through valleys. Past contests taught you that a large change in altitude ruins your performance, so you decide to ride the route with the smallest altitude difference. The altitude difference of a route is the difference between the highest and the lowest altitude on it. Write a program that finds such a route.

You are given the number of crossings and the altitude of each crossing, together with the roads that connect the crossings.

Your program must find the route that minimizes the difference between the highest and the lowest point on the route. If several routes share that difference, take the shortest one.

The picture below shows one example.

The shortest route from 1 to 7 runs through 2, 3 and 4, but its altitude difference is 8. Riding through 5, 6 and 4 instead brings the altitude difference down to 2. Going from 6 straight to 7 gives the same altitude difference, but that route is longer.

The first line holds an integer $t$ ($1 \le t \le 100$), the number of test cases. Each test case is given as follows.

• One line with two integers $n$ ($1 \le n \le 100$) and $m$ ($0 \le m \le 5000$), the number of crossings and the number of roads. The crossings are numbered $1$ through $n$.
• $n$ lines, the $i$-th of which holds one integer $h_i$ ($0 \le h_i \le 10^9$), the altitude of crossing $i$.
• $m$ lines with three integers $a_j$, $b_j$ ($1 \le a_j, b_j \le n$) and $c_j$ ($1 \le c_j \le 10^6$). This means there is a two-way road of length $c_j$ between crossings $a_j$ and $b_j$. The altitude along a road changes linearly between its two crossings.

You start at crossing 1 and the contest is at crossing $n$. Reaching crossing $n$ from crossing 1 is always possible.

For each test case, print one line with two integers separated by a single space. The first is the smallest altitude difference, and the second is the length of the shortest route that has that altitude difference.