该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在银河联邦的贸易航线网络中，星港之间通过常规航道相连。每条航道的航行时间已知且为非负整数。为了促进贸易，联邦准备在所有现有航道中选择恰好一条，授予“折跃许可”：
持证船只在规划航线时，可以把这条航道视为一条“折跃通道”——通过它的两端星港实现瞬时折跃（不计时间）。

贸易署有一批固定的货运委托，每个委托要求从起点星港运送到终点星港。你需要决定授予哪一条航道折跃许可，使得所有委托的最短运输时间总和最小。

题目描述

给定一个包含 $n$ 个星港、$m$ 条无向航道的带权图（边权表示航行时间）。另有 $k$ 个货运委托，第 $j$ 个委托给出一对星港 $(a_j, b_j)$。

你必须从现有的 $m$ 条航道中选择恰好一条航道 $(x, y)$ 作为“折跃许可航道”。

你的任务是：选择一条航道作为折跃许可，使得 $k$ 个委托的上述最短时间之和最小，并输出这个最小值。

输入格式

第一行三个整数 $n, m, k$。
接下来 $m$ 行，每行三个整数 $u, v, w$，表示星港 $u$ 与 $v$ 之间有一条无向航道，航行时间为 $w$。
接下来 $k$ 行，每行两个整数 $a, b$，表示一个货运委托的起点与终点。

输出格式

输出一个整数，表示最小可能的总运输时间。

输入输出样例

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

22

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

13

数据范围与约定

• $2 ≤ n ≤ 1000$
• $n − 1 ≤ m ≤ min(1000, n(n − 1) / 2)$
• $1 ≤ k ≤ 1000$
• $1 ≤ u, v ≤ n$，$u ≠ v$
• $1 ≤ w ≤ 1000$
• 不存在重边
• 允许 $a_j = b_j$
• 允许多个委托重复

测试点设计（共20点）

测试点编号	规模与特点
1–10	$n \le 80, m \le 200, k \le 300$
11–20	无约束