### 问题描述 在一个遥远的星球上，有 $n$ 个岛屿，由 $m$ 条海底道路连接。每个隧道都有其特定的维护成本。由于星球的天气极端不稳定，为了确保岛屿之间的交通，政府决定对某些道路进行加固。 加固道路的策略是这样的：从一个岛屿到另一个岛屿的任何路径中，都至少有一个道路选择中的所有道路都被加固。但是，由于财政压力，政府希望在满足上述策略的前提下，使得加固的隧道的维护成本总和最小。 但是这个问题有个附加条件：为了保护某些生态脆弱的海域，其中有 $k$ 对岛屿之间的隧道是不允许加固的。 你的任务是，决定哪些隧道需要加固。题目保证一定存在合理的答案。 ### 输入格式 第一行包含三个整数 $n$，$m$ 和 $k$。 接下来的 $m$ 行，每行包含三个整数 $a$，$b$ 和 $c$，表示岛屿 $a$ 和 $b$ 之间有一条隧道，其维护成本为 $c$。 接下来的 $k$ 行，每行包含两个整数 $x$ 和 $y$，表示岛屿 $x$ 和 $y$ 之间的隧道是不允许加固的。 ### 输出格式 第一行输出最低的加固隧道的维护成本总和。 第二行输出选中加固的隧道数量 $p$。 ### 样例输入 ``` 5 6 1 1 2 5 1 3 4 2 3 3 2 4 2 3 5 1 4 5 6 3 5 ``` ### 样例输出 ``` 15 4 ``` ### 测评数据规模 对于 $40$% 的数据，$2 \le n \le 30$。 对于 $80$% 的数据，$2 \le n \le 300$。 对于 $100$% 的数据，$2 \le n \le 10^4$，$n-1 \le m \le 2\times 10^5$，$1 \le c \le 1000$，$0 \le k \le min(10^4, n-m-1)$。