소 통행료 경로

농부 존은 언제나 수익을 늘릴 방법을 찾고 있어서, 소가 농장의 길을 지날 때마다 내야 하는 통행료를 매겼다.

농장에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 목초지가 있다 ($1 \le N \le 250$). 목초지들은 $M$개의 양방향 길로 연결되어 있으며 ($1 \le M \le 10{,}000$), $j$번째 길은 서로 다른 두 목초지 $A_j$와 $B_j$ ($1 \le A_j, B_j \le N$)를 잇고 간선 통행료 $L_j$ ($1 \le L_j \le 100{,}000$)를 가진다. 같은 두 목초지를 잇는 길이 여러 개 있을 수 있지만, 어떤 길도 한 목초지를 자기 자신과 잇지는 않는다. 임의의 목초지에서 다른 임의의 목초지로 항상 갈 수 있으므로 그래프는 연결되어 있다.

또한 각 목초지 $i$에도 통행료 $C_i$ ($1 \le C_i \le 100{,}000$)가 매겨져 있다. 한 목초지에서 다른 목초지로 가는 이동 비용은, 지나간 모든 길의 간선 통행료의 합에, 이동 중 지난 모든 목초지(출발 목초지와 도착 목초지 포함)의 통행료 중 최댓값을 한 번 더한 값이다.

소들은 여러 선택지를 비교하고 싶어 한다. $K$개의 질의에 답하라 ($1 \le K \le 10{,}000$). $i$번째 질의는 출발 목초지 $s_i$와 도착 목초지 $t_i$ ($s_i \ne t_i$)로 주어지며, $s_i$에서 $t_i$로 가는 이동 비용의 최솟값을 출력해야 한다.

예시. 목초지가 다섯 개이고 각 목초지의 통행료가 $C_1=2$, $C_2=5$, $C_3=3$, $C_4=3$, $C_5=4$이며, 간선 통행료가 $(1,2)=3$, $(1,3)=2$, $(2,5)=3$, $(3,5)=1$, $(4,5)=1$, $(2,4)=3$, $(3,4)=4$라고 하자. 여기서 $(a,b)=w$는 목초지 $a$와 $b$ 사이의 길의 간선 통행료가 $w$임을 뜻한다.

목초지 $1$에서 $4$로 갈 때 $1 \to 3 \to 5 \to 4$ 경로를 택하면, 간선 통행료의 합은 $2+1+1=4$이고 경로에서 가장 큰 목초지 통행료는 $4$(목초지 $5$)이므로 총 비용은 $4+4=8$이다.

목초지 $2$에서 $3$으로 갈 때 $2 \to 5 \to 3$ 경로를 택하면, 간선 통행료의 합은 $3+1=4$이고 가장 큰 목초지 통행료는 $5$(목초지 $2$)이므로 총 비용은 $4+5=9$이다.

• 첫째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다.
• 다음 $N$개의 줄에는 각각 정수 하나가 주어진다. 그중 $i$번째 줄의 값은 목초지 $i$의 통행료 $C_i$이다.
• 다음 $M$개의 줄에는 각각 세 정수 $A_j$, $B_j$, $L_j$가 공백으로 구분되어 주어지며, 목초지 $A_j$와 $B_j$를 잇는 간선 통행료 $L_j$의 양방향 길을 나타낸다.
• 다음 $K$개의 줄에는 각각 두 정수 $s_i$와 $t_i$가 공백으로 구분되어 주어지며, 하나의 질의를 이룬다.

• $K$개의 줄을 출력한다. $i$번째 줄에는 $s_i$에서 $t_i$로 가는 이동 비용의 최솟값인 정수 하나를 출력한다.