Fugitive Monkey

A monkey has escaped from a zoo and wants to travel from a start city to a destination city as quickly as possible. The country has N cities and bidirectional roads between some pairs of cities. Each road takes a fixed amount of time to traverse.

The monkey's old enemy, a dog, will delay the monkey in one city on the chosen route. The start city and destination city are also part of the route. Each city has its own delay time, and the dog chooses the city on the route where it can delay the monkey for the longest time.

Therefore, the total time of a route is the sum of its road travel times plus the maximum delay time among all cities on that route. For each query, find the minimum possible total time from city S to city T.

Suppose there are four cities A, B, C, and D, and the monkey moves from A to D. If the road travel time of A-B-D is 100 and that of A-C-D is 140, A-B-D is faster by roads alone. However, if the delay times of the four cities are 10, 80, 20, and 10, the total times become 180 and 160, so A-C-D is faster.

The first line contains the number of cities N (2 <= N <= 500), the number of roads M (0 <= M <= 10,000), and the number of queries Q (0 <= Q <= 40,000).

The next line contains N integers. The i-th integer is the delay time in city i, and each value is between 1 and 10,000 inclusive.

Each of the next M lines contains three integers a, b, and d, meaning that there is a bidirectional road between cities a and b with travel time d. Here 1 <= a, b <= N, and d is between 1 and 10,000 inclusive.

Each of the next Q lines contains two integers S and T, the start city and destination city for one query.

For each query, print one line containing the minimum total time needed to escape from city S to city T. If there is no route between the two cities, print -1.