Cow Toll Paths

Farmer John is always looking for ways to increase his revenue, so he has set up tolls that the cows must pay whenever they walk along the paths of his farm.

The farm has $N$ pastures ($1 \le N \le 250$), numbered $1$ through $N$. They are connected by $M$ bidirectional paths ($1 \le M \le 10{,}000$); path $j$ joins two different pastures $A_j$ and $B_j$ ($1 \le A_j, B_j \le N$) and has an edge toll $L_j$ ($1 \le L_j \le 100{,}000$). Two pastures may be joined by more than one path, but no path connects a pasture to itself. Every pasture can be reached from every other pasture, so the graph is connected.

In addition, each pasture $i$ has its own toll $C_i$ ($1 \le C_i \le 100{,}000$). The cost of a trip from one pasture to a different pasture is the sum of the edge tolls of all paths traversed, plus a single additional toll equal to the maximum pasture toll among all pastures visited on the trip, including the starting and ending pastures.

The cows want to compare their options. Answer $K$ queries ($1 \le K \le 10{,}000$). Query $i$ gives a starting pasture $s_i$ and an ending pasture $t_i$ ($s_i \ne t_i$); output the minimum possible cost of a trip from $s_i$ to $t_i$.

Worked example. Consider five pastures with pasture tolls $C_1=2$, $C_2=5$, $C_3=3$, $C_4=3$, $C_5=4$, connected by paths with edge tolls $(1,2)=3$, $(1,3)=2$, $(2,5)=3$, $(3,5)=1$, $(4,5)=1$, $(2,4)=3$, $(3,4)=4$, where $(a,b)=w$ means the path between pastures $a$ and $b$ has edge toll $w$.

To travel from pasture $1$ to pasture $4$, take $1 \to 3 \to 5 \to 4$: the edge tolls sum to $2+1+1=4$ and the largest pasture toll on the route is $4$ (pasture $5$), so the total cost is $4+4=8$.

To travel from pasture $2$ to pasture $3$, take $2 \to 5 \to 3$: the edge tolls sum to $3+1=4$ and the largest pasture toll on the route is $5$ (pasture $2$), so the total cost is $4+5=9$.

• The first line contains three space-separated integers $N$, $M$, and $K$.
• Each of the next $N$ lines contains one integer; the $i$-th of them is $C_i$, the toll of pasture $i$.
• Each of the next $M$ lines contains three space-separated integers $A_j$, $B_j$, and $L_j$, describing a bidirectional path between pastures $A_j$ and $B_j$ with edge toll $L_j$.
• Each of the next $K$ lines contains two space-separated integers $s_i$ and $t_i$, giving one query.

• Output $K$ lines. The $i$-th line contains a single integer: the minimum possible cost of a trip from $s_i$ to $t_i$.