Reducing Delivery Cost
Contest: Codeforces Round 677 (Div. 3)
Difficulty rating: 2100
Tags: brute force, graphs, shortest paths

You are a mayor of Berlyatov. There are $$$n$$$ districts and $$$m$$$ two-way roads between them. The $$$i$$$-th road connects districts $$$x_i$$$ and $$$y_i$$$. The cost of travelling along this road is $$$w_i$$$. There is some path between each pair of districts, so the city is connected.

There are $$$k$$$ delivery routes in Berlyatov. The $$$i$$$-th route is going from the district $$$a_i$$$ to the district $$$b_i$$$. There is one courier on each route and the courier will always choose the cheapest (minimum by total cost) path from the district $$$a_i$$$ to the district $$$b_i$$$ to deliver products.

The route can go from the district to itself, some couriers routes can coincide (and you have to count them independently).

You can make at most one road to have cost zero (i.e. you choose at most one road and change its cost with $$$0$$$).

Let $$$d(x, y)$$$ be the cheapest cost of travel between districts $$$x$$$ and $$$y$$$.

Your task is to find the minimum total courier routes cost you can achieve, if you optimally select the some road and change its cost with $$$0$$$. In other words, you have to find the minimum possible value of $$$\sum\limits_{i = 1}^{k} d(a_i, b_i)$$$ after applying the operation described above optimally.

Input format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
6 5 2
1 2 5
2 3 7
2 4 4
4 5 2
4 6 8
1 6
5 3

Example output:
22

Example 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

Example output:
13

Editorial:
If we would naively solve the problem, we would just try to replace each edge's cost with zero and run Dijkstra algorithm $$$n$$$ times to get the cheapest paths. But this is too slow.
Let's try to replace each edge's cost with zero anyway but use some precalculations to improve the speed of the solution. Let's firstly run Dijkstra $$$n$$$ times to calculate all cheapest pairwise paths. Then, let's fix which edge we "remove" $$$(x, y)$$$.
There are three cases for the path $$$(a, b)$$$: this edge was not on the cheapest path before removing and is not on the cheapest path after removing. Then the cost of this path is $$$d(a, b)$$$. The second case is when this edge was not on the cheapest path before removing but it is on the cheapest path after removing. Then the cost of this path is $$$min(d(a, x) + d(y, b), d(a, y) + d(x, b))$$$. So we are just going from $$$a$$$ to $$$x$$$ using the cheapest path, then going through the zero edge and then going from $$$y$$$ to $$$b$$$ using the cheapest path also (or vice versa, from $$$a$$$ to $$$y$$$ and from $$$x$$$ to $$$b$$$). And the third case is when this edge was already on the cheapest path between $$$a$$$ and $$$b$$$ but this case is essentially the same as the second one.
So, if we fix the edge $$$(x, y)$$$, then the answer for this edge is $$$\sum\limits_{i=1}^{k} min(d(a_i, b_i), d(a_i, x) + d(y, b_i), d(a_i, y) + d(x, b_i))$$$. Taking the minimum over all edges, we will get the answer.
The precalculating part works in $$$O(n m \log n)$$$ and the second part works in $$$O(k m)$$$.