CF1433G.Reducing Delivery Cost

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.

你是一名贝利亚托夫市的市长。该市共有 $n$ 个区和 $m$ 条双向道路连接这些区。第 $i$ 条道路连接区 $x_i$ 和 $y_i$，通行成本为 $w_i$。任意两个区之间均存在路径，因此该城市是连通的。

贝利亚托夫市共有 $k$ 条快递运输路线。第 $i$ 条路线从区 $a_i$ 出发，到达区 $b_i$。每条路线上均有一名快递员，且该快递员总是选择总成本最低（即最短路径）的路线，从区 $a_i$ 前往区 $b_i$ 完成配送任务。

路线允许起点与终点为同一区（即 $a_i = b_i$），不同快递员的路线可能重合（此时需独立计数）。

你最多可将一条道路的成本设为零（即：你至多选择一条道路，并将其通行成本修改为 $0$）。

令 $d(x, y)$ 表示区 $x$ 与区 $y$ 之间的最低通行成本。

你的任务是：在最优地选择至多一条道路并将其成本设为 $0$ 后，使得所有快递路线的总成本 $\sum\limits_{i = 1}^{k} d(a_i, b_i)$ 达到最小。请找出该最小可能值。

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

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 1000$；$n - 1 \le m \le \min(1000, \frac{n(n-1)}{2})$；$1 \le k \le 1000$），分别表示行政区的数量、道路的数量以及快递路线的数量。

接下来的 $m$ 行描述道路。第 $i$ 条道路由三个整数 $x_i$、$y_i$ 和 $w_i$（$1 \le x_i, y_i \le n$；$x_i \ne y_i$；$1 \le w_i \le 1000$）给出，其中 $x_i$ 和 $y_i$ 是该道路所连接的两个行政区，$w_i$ 是该道路的费用。保证任意两个行政区之间均存在路径，即整个城市是连通的。同时保证任意两个行政区之间至多只有一条道路。

接下来的 $k$ 行描述快递路线。第 $i$ 条路线由两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$）给出，表示该路线的起止行政区。路线允许起点与终点为同一行政区；部分快递路线可能完全相同（需独立计数）。

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.

输出一个整数——在最多将一条道路的费用设为 0 的前提下，所能达到的快递员总路线费用的最小值（即最小化 $\sum\limits_{i=1}^{k} d(a_i, b_i)$，其中 $d(x, y)$ 表示从区域 $x$ 到区域 $y$ 的最便宜通行费用）。

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

第一个示例对应的图：

在此图中，你可以选择道路 $(2, 4)$ 或道路 $(4, 6)$。两种选择均导致总代价为 $22$。

第二个示例对应的图：

在此图中，你可以选择道路 $(3, 4)$。这将导致总代价为 $13$。