Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3901
Travel

Time Limit: 1 Second      Memory Limit: 65536 KB

After ACM summer training, Bob and his girlfriend Alice want to travel together.

In their country, there are n citys (indexed from 1 to n) and m expressways between the n citys. If you want to go through an expressway, you need to pay some highway toll fee for this expressway. And as we know, Alice likes shopping very much. So Alice will ask Bob to buy gifts for her in the city which has the most expensive gift in their travel path.

Bob and Alice have q plans. Each plan contains a start A and a destination city B. Now give you the price of gift in each city and the highway toll fee for each expressway. For each plan, can you tell Bob how much money does he spend at least?

Input

The first line of input contains an integer T (T ≤ 20). T is the number of the cases.

For each test cases, the first line is three integers n (2≤ n ≤300), the number of cities, m (1≤ m ≤100000), q (1≤ q ≤100000), the number of queries.

In the second line, there are n integers pi (1≤ pi ≤100000). pi means the price of gift in the city i .

Then following m lines, each line contains three integers x, y, t (1≤ t ≤100000), which means there are an expressway between city x and city y, and the highway toll fee of it is t.

Then following q lines, each line contains two integers s and d , which means the start city is s and the destination city is d.

You should notice that two cities could have more than one road connecting them. And there are no self loops in the graph. We guarantee there are at least one path between any different cities.

Output

For each query of each test case, output the minimum cost of Bob.

Sample Input

2
5 7 2
1 2 3 4 5
1 2 2
2 3 10
1 5 2
2 5 2
3 5 2
1 4 2
4 5 2
2 3
4 2
3 2 1
5 7 1
1 2 10
2 3 14
1 3

Sample Output

9
8
31

Hint

For the first case:

The best way from 2 to 3 is : 2->5->3

The best way from 4 to 2 is : 4->1->2


Author: LIN, Xi
Source: ZOJ Monthly, September 2015
Submit    Status