URI Online Judge | 1947

Cab Driver Route

By Cristhian Bonilha, UTFPR Brazil

Timelimit: 2

An important event is happening today in your city, and there are many tourists lost. To get to their destinations in this unknown city they usually order cabs. You have been hired to help the cab drivers, who are overwhelmed with so many orders.

The city can be represented with N reference points, and M roads that connect such points. Each road has a length, and there will always exist a path between any two distinct points of the city.

The cab driver goal is to answer to K orders. Each order consists of two points in the city, O and D (source and destiny), where the tourist is currently at the point O and wants to get to the point D. The cab driver is initially in the point 1, he intends to answer only one order at each time (in any order he wants), and after the last order he must return to the point 1.

For example, consider a city with N = 5 reference points and K = 2 tourists, where the first tourist wants to get from point 4 to point 3, and the second wants to get from point 2 to point 4. Therefore, the cab driver has two possible routes: 1 -> 4 -> 3 -> 2 -> 4 -> 1; or 1 -> 2 -> 4 -> 3 -> 1. Notice that A -> B represents a path between the points A and B, which consists of one or more roads.

Puzzled with so many route options and wanting to save fuel, the cab driver asked you to calculate which route has the minimum travelled distance.

Input

Each test case starts with three integers N, M and K (2 ≤ N ≤ 104, N-1 ≤ M ≤ 105, 1 ≤ K ≤ 15).

Following there will be M rows, each with three integers A, B and C each, representing that there is a road that connects the points A and B, which can be travelled in both directions, with length C (1 ≤ A, BN, 1 ≤ C ≤ 100, A <> B).

Following there will be K rows, each with two integers O and D each, representing that there is a tourist who wants to get from point O to point D (1 ≤ O, DN, O <> D).

Output

For each test case you should print one line containing one integer, representing the minimum possible distance to be travelled if the cab driver starts at point 1, answer all the orders (one at a time), and come back to point 1.

Input Samples Output Samples

3 3 1
1 2 2
2 3 4
3 1 3
2 3

9

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

26