You are a mayor of Berlyatov.有 $$$n$$$ 个区,它们之间有 $$$m$$$ 双向道路。第 $$$i$$$ 条道路连接 $$$x_i$$$ 区和 $$$y_i$$$ 区。沿着这条路行驶的费用为$$$w_i$$$。每对区域之间都有一些路径,因此城市是相连的。
Berlyatov 有 $$$k$$$ 送货路线。第 $$$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)$$$ 的最小可能值。
输入
输入的第一行包含三个整数 $$$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$$$ 是第 $$$i$$$ 条道路连接的地区,$$$w_i$$$ 是其成本。保证每对区域之间都有路径,因此城市是相连的。还保证每对区域之间最多有一条道路。
接下来的 $$$k$$$ 行描述快递路线。第 $$$i$$$ 条路线由两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) 给出 - 第 $$$i$$$ 条路线的地区。路线可以从区到本区,有些快递路线可以重合(需要单独统计)。
输出
打印一个整数 - 如果您可以修建一些(最多一条)道路,您可以实现的最低总快递路线成本(即最小值 $$$\sum\limits_{i=1}^{k} d(a_i, b_i)$$$,其中 $$$d(x, y)$$$ 是地区 $$$x$$$ 和 $$$y$$$ 之间最便宜的旅行成本)成本为零。
示例
输入 #1
6 5 2 1 2 5 2 3 7 2 4 4 4 5 2 4 6 8 1 6 5 3
输出 #1
22
输入 #2
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
输出 #2
13
注意
第一个例子对应的图片:
在那里,您可以选择道路 $$$(2, 4)$$$ 或道路 $$$(4, 6)$$$。 Both options lead to the total cost $$$22$$$.
第二个例子对应的图片:
在那里,你可以选择道路$$$(3, 4)$$$。 This leads to the total cost $$$13$$$.