도망자 원숭이

동물원에서 탈출한 원숭이는 시작 도시에서 도착 도시까지 가능한 한 빨리 이동하려고 한다. 이 나라는 N개의 도시와 몇몇 도시 쌍을 잇는 양방향 도로로 이루어져 있다. 각 도로를 지날 때마다 정해진 시간이 걸린다.

원숭이의 오랜 숙적인 멍멍이는 원숭이가 선택한 경로 위의 도시 중 한 곳에서 원숭이를 괴롭힌다. 시작 도시와 도착 도시도 경로에 포함된다. 도시마다 멍멍이가 원숭이를 붙잡아 둘 수 있는 시간이 다르며, 멍멍이는 그 경로에 포함된 도시들 중 가장 오래 괴롭힐 수 있는 도시를 고른다.

따라서 어떤 경로의 총 시간은 도로 이동 시간의 합에, 그 경로에 포함된 도시들의 괴롭힘 시간 최댓값을 더한 값이다. 여러 질문이 주어질 때마다 시작 도시 S에서 도착 도시 T까지 가능한 최소 총 시간을 구하시오.

네 도시 A, B, C, D가 있고 원숭이가 A에서 D로 이동한다고 하자. A-B-D의 도로 이동 시간이 100이고 A-C-D의 도로 이동 시간이 140이라면 도로만 보면 A-B-D가 더 빠르다. 하지만 네 도시의 괴롭힘 시간이 10, 80, 20, 10이라면 총 시간은 각각 180과 160이 되어 A-C-D가 더 빠르다.

첫 줄에 도시의 개수 N (2 <= N <= 500), 도로의 개수 M (0 <= M <= 10,000), 질문의 개수 Q (0 <= Q <= 40,000)가 주어진다.

다음 줄에 N개의 정수가 주어진다. i번째 정수는 i번 도시에서 멍멍이가 원숭이를 괴롭힐 수 있는 시간이며, 각 값은 1 이상 10,000 이하이다.

이어서 M줄에 걸쳐 세 정수 a, b, d가 주어진다. 이는 a번 도시와 b번 도시를 잇는 양방향 도로가 있고, 그 도로의 통행 시간이 d라는 뜻이다. 여기서 1 <= a, b <= N이고, d는 1 이상 10,000 이하이다.

이어서 Q줄에 걸쳐 두 정수 S, T가 주어진다. 이는 한 질문의 출발 도시와 도착 도시이다.

각 질문마다 한 줄에 S번 도시에서 T번 도시까지 도망가는 데 필요한 최소 총 시간을 출력한다. 두 도시 사이에 경로가 없으면 -1을 출력한다.