SP11718 ROIM - Boa viagem, Roim

计算机工程专业的学生 Roim 正在为一次到墨西哥的旅行做准备。为了更好安排这次旅行，他仔细研究了航班网络，掌握了所有 **N** 个机场上运营的 **R** 个常规航班的情况。令人头疼的是，他有个同学特别烦人，总是不断地打扰他。 为了解决这个问题，Roim 计划设计两份不同的飞行计划：一份给他所在的团队，另一份给那个烦人的家伙。条件是，这两个飞行计划不能有相同的航班（需要注意的是，这两个计划可以经过相同的机场，只是不能使用相同的航班，即使这些航班的时间不同也是不允许的）。只靠常规航班可能无法满足这个条件，所以他考虑使用最多 **C** 个由旅行社包租的航班。然而，由于包机航班常常会有较大延误，他希望尽量减少它们的使用。当然，在优先选择包机航班数量最少的情况下，Roim 也会选择总成本最低的方案（总成本定义为所使用航班的费用之和）。

输入由多个测试用例组成。每个测试用例的第一行包含三个整数 **N** (2 ≤ N ≤ 100)、**R** (0 ≤ R ≤ 1000) 和 **C** (0 ≤ C ≤ 100)。 接下来的 **R** 行中，每行包含三个整数 **a**、**b** (0 ≤ a, b < N, a ≠ b) 和 **c** (1 ≤ c ≤ 1000)，表示从机场 **a** 到机场 **b** 的常规航班的费用为 **c**。 接下来的 **C** 行中，每行包含三个整数 **a**、**b** (0 ≤ a, b < N, a ≠ b) 和 **c** (1 ≤ c ≤ 1000)，表示从机场 **a** 到机场 **b** 的包机航班的费用为 **c**。 假设任何一对城市之间至多只有单向的一条航班连接。

如果可以设计出这两份飞行计划，输出两个整数，以空格分隔。第一个整数表示所使用的包机航班的最少数量，第二个整数表示方案的总成本。 如果无法规划出两个都能到达目的地的飞行计划，则输出「Boa viagem, Roim」。 **本翻译由 AI 自动生成**