자전거 여행

자전거를 타고 프로그래밍 대회장까지 가려고 한다. 대회장으로 가는 가장 짧은 길은 산꼭대기를 넘고 골짜기를 지나갈 수도 있다. 지금까지 겪어 보니 고도가 크게 오르내린 날은 대회 성적이 나빴다. 그래서 고도 차가 가장 작은 경로로 가기로 했다. 경로의 고도 차는 그 경로에서 가장 높은 지점의 고도와 가장 낮은 지점의 고도의 차이다. 이런 경로를 찾는 프로그램을 작성하시오.

입력으로는 교차로의 개수와 각 교차로의 고도, 그리고 교차로를 잇는 도로가 주어진다.

프로그램은 경로에서 가장 높은 지점과 가장 낮은 지점의 고도 차를 가장 작게 만드는 경로를 찾아야 한다. 그런 경로가 여럿이면 그중 가장 짧은 것을 고른다.

아래 그림이 한 가지 예다.

1번에서 7번으로 가는 가장 짧은 경로는 2번, 3번, 4번을 지나지만 고도 차가 8이다. 대신 5번, 6번, 4번을 지나면 고도 차가 2로 줄어든다. 6번에서 7번으로 곧장 가도 고도 차는 똑같지만 경로가 더 길다.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 100$)가 주어진다. 각 테스트 케이스는 다음과 같이 이루어진다.

• 첫째 줄에 교차로의 개수 $n$ ($1 \le n \le 100$)과 도로의 개수 $m$ ($0 \le m \le 5000$)이 공백을 사이에 두고 주어진다. 교차로에는 $1$번부터 $n$번까지 번호가 매겨져 있다.
• 다음 $n$개 줄에 $i$번 교차로의 고도 $h_i$ ($0 \le h_i \le 10^9$)가 한 줄에 하나씩 주어진다.
• 다음 $m$개 줄에 세 정수 $a_j$, $b_j$ ($1 \le a_j, b_j \le n$)와 $c_j$ ($1 \le c_j \le 10^6$)가 주어진다. $a_j$번 교차로와 $b_j$번 교차로를 잇는 길이 $c_j$의 양방향 도로가 있다는 뜻이다. 도로 위의 고도는 두 교차로 사이에서 일정한 비율로 변한다.

출발점은 1번 교차로이고 대회장은 $n$번 교차로에 있다. 1번 교차로에서 $n$번 교차로까지 가는 방법은 항상 존재한다.

각 테스트 케이스마다 두 정수를 공백 하나로 구분해 한 줄에 출력한다. 앞의 정수는 가장 작은 고도 차이고, 뒤의 정수는 그 고도 차를 갖는 가장 짧은 경로의 길이다.