Problem D
Queen in the East

After overthrowing the corrupted council in the city of Meereen, the woman known to the people as Mother of Dragons is now the Queen in the East. Her plan is not to conquer the East, however; her plan is to conquer the west world known as Westeros. She has gathered the warriors and the ships, and together with her advisors and her dragons, she has set her destination as King’s Landing, the capital city of Westeros where the king resides.

Her advisors are now looking at the map trying to figure out a route that will take them to King’s Landing as soon as possible. However, due to the unfriendly terrain and unfamiliar territory, the shortest route may not be the easiest route. Furthermore, the group will need to visit cities along the way to oversee the people under the Queen’s reign, and so that her men can rest and her dragons can be fed.

The map shows the cities, and the Queen’s advisors can determine the time (in days) that it takes to get from one city to another. For each city in the map, they have also calculated the time (in days) that it takes to fully feed the dragons. The dragons will only need to be fed once during the whole trip, which must be in a city after the longest journey from one city and another on their chosen route. The Queen and her advisors need your help to find the fastest route to King’s Landing.

Input

The input my contain multiple test cases. The first line of each test case contains three integers C($\leq 80$), P($\leq 1000$) and Q($\leq 6320$), where C indicates the number of cities (cities are numbered using distinct integers ranging from 1 to C), P represents the number of paths, and Q is the number of queries. The next line contains C integers where the the i-th integer $\textit{f}_\textit {i}$ is the time (in days) of feeding the dragons in city i. Each of the next P lines contains three integers: $\textit{c}_1$, $\textit{c}_2$ ($\neq $ $\textit{c}_1$), and d indicating that the time to travel from city $\textit{c}_1$ to $\textit{c}_2$ (or from $\textit{c}_2$ to $\textit{c}_1$) is d days. Each of the next Q lines contains two integers $\textit{c}_1$ and $\textit{c}_2$ ($\textit{c}_1$ $\neq $ $\textit{c}_2$) asking for the time (in days) of the fastest route from city $\textit{c}_1$ to city $\textit{c}_2$. The input will terminate with three zeros from C, P, Q.

Output

For each test case in the input, you must first output the test case number (starting from 1) as shown in the sample output. Then for each query in the input, you must print a line giving the minimum time (in days) of going from the first city to the second city in the query. If there exists no path between them, just print ‘-1’. Print a blank line between two consecutive test cases.

7 6 5
6 19 5 15 2 7 21
4 7 91
1 3 92
5 7 36
1 4 94
3 4 21
6 5 18
4 1
6 4
1 7
6 4
4 3
7 6 5
25 22 24 2 3 14 20
1 7 16
3 1 60
5 2 84
2 1 12
6 5 37
2 4 27
6 2
2 5
2 6
4 3
4 7
0 0 0

1
109
166
206
166
36

2
143
106
143
124
80