Description

Like everyone else, FJ is always thinking up ways to increase his revenue. To this end, he has set up a series of tolls that the cows will pay when they traverse the cowpaths throughout the farm.

The farm is modeled as an undirected graph with $N$ pastures, conveniently numbered $1..N$, connected by $M$ bidirectional cowpaths. Path $j$ connects two different pastures $A_j$ and $B_j$ and has an edge toll $L_j$. There may be multiple cowpaths connecting the same pair of pastures, but no cowpath connects a pasture to itself. The graph is connected, so a cow can always move from any pasture to any other pasture by following some sequence of cowpaths.

FJ has also assigned a toll $C_i$ to every pasture $i$. The cost of traveling from pasture $s$ to a different pasture $t$ along any path is the sum of the edge tolls on that path plus a single additional toll equal to the maximum of all the node tolls encountered along the way, including $s$ and $t$.

You are given $K$ queries. Query $i$ specifies $(s_i, t_i)$ and asks for the minimum possible cost of a trip from $s_i$ to $t_i$ under the rule above.

Input Format

• Line $1$: Three space-separated integers $N$, $M$, and $K$.
• Lines $2..N+1$: Line $i+1$ contains a single integer $C_i$.
• Lines $N+2..N+M+1$: Line $j+N+1$ contains three space-separated integers $A_j$, $B_j$, and $L_j$.
• Lines $N+M+2..N+M+K+1$: Line $i+N+M+1$ contains two space-separated integers $s_i$ and $t_i$.

Output Format

• Lines $1..K$: Line $i$ contains a single integer, the minimum cost of any route from $s_i$ to $t_i$.

5 7 2 
2 
5 
3 
3 
4 
1 2 3 
1 3 2 
2 5 3 
5 3 1 
5 4 1 
2 4 3 
3 4 4 
1 4 
2 3 

8 
9 

Hint

Constraints: $1 \leq N \leq 250$, $1 \leq M \leq 10^4$, $1 \leq K \leq 10^4$, $1 \leq C_i \leq 100{,}000$, $1 \leq L_j \leq 100{,}000$.

Notes: Multiple edges between a pair of pastures are allowed, but self-loops are not. The graph is connected.

Translated by ChatGPT 5