Reducing Delivery Cost

Description:

Input:

The first line of the input contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 1000$$$; $$$n - 1 \le m \le min(1000, \frac{n(n-1)}{2})$$$; $$$1 \le k \le 1000$$$) — the number of districts, the number of roads and the number of courier routes.

The next $$$m$$$ lines describe roads. The $$$i$$$-th road is given as three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le w_i \le 1000$$$), where $$$x_i$$$ and $$$y_i$$$ are districts the $$$i$$$-th road connects and $$$w_i$$$ is its cost. It is guaranteed that there is some path between each pair of districts, so the city is connected. It is also guaranteed that there is at most one road between each pair of districts.

The next $$$k$$$ lines describe courier routes. The $$$i$$$-th route is given as two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — the districts of the $$$i$$$-th route. The route can go from the district to itself, some couriers routes can coincide (and you have to count them independently).

Output:

Print one integer — the minimum total courier routes cost you can achieve (i.e. the minimum value $$$\sum\limits_{i=1}^{k} d(a_i, b_i)$$$, where $$$d(x, y)$$$ is the cheapest cost of travel between districts $$$x$$$ and $$$y$$$) if you can make some (at most one) road cost zero.

Sample Input:

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

Sample Output:

22

Sample Input:

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

Sample Output:

13

Note:

The picture corresponding to the first example:

There, you can choose either the road $$$(2, 4)$$$ or the road $$$(4, 6)$$$. Both options lead to the total cost $$$22$$$.

The picture corresponding to the second example:

There, you can choose the road $$$(3, 4)$$$. This leads to the total cost $$$13$$$.