{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"G 先生的工作是导游。他当前的任务是将一些游客从一个城市带到另一个城市。一些双向道路将城市连通。每对相邻的城市之间,有一条巴士线路只在这两个城市之间运营,并使用了直接连接这两个城市的道路。每条巴士线路有一个载客人数的上限。G 先生有一张地图,显示了各城市和它们之间的连接道路。他也知道各条巴士线路的信息。他明白,要将全部的乘客带到目标城市,未必能够以单次旅程完成。\n\n例如,考虑下图中的 7 个城市。连接城市的边表示道路,每条边上的数表示该巴士线路的载客上限。\n\n![巴士线路图示](https://cdn.vijos.org/fs/94e594529d0863c41e76e23b94608bd05882bafa)\n\n现在,他想带 99 名游客,从城市 1 前往城市 7,那么他将需要至少 5 次旅程,并且路线应当是:1 - 2 - 4 - 7。\n\nG 先生难以自己找出最佳路线,用最少的旅程次数将全部的游客带到目标城市。因此,他向你求助。\n\n## 输入\n\n输入包括一组或多组测试数据。对于每组测试数据,第 1 行包含两个整数 N, R,其中 N (N ≤ 100) 表示城市的数目,R 表示道路的条数。接下来的 R 行,每行包含三个整数 C_1, C_2, P,其中 C_1, C_2 是城市编号,P (P \u003e 1) 是这两个城市间巴士线路的载客上限。城市编号都是介于从 1 到 N 之间的正整数。第 R + 1 行包含三个整数:S, D, T,分别表示起始城市、目标城市的编号,以及导游需要带领的游客数目。\n\n输入以 N, R 皆等于 0 结束。\n\n## 输出\n\n对于每组测试数据,在第 1 行输出测试数据分组的编号,在第 2 行输出最少的旅程次数。每组测试数据之后,打印一个空白行。\n\n## 示例输入\n```\n7 10\n1 2 30\n1 3 15\n1 4 10\n2 4 25\n2 5 60\n3 4 40\n3 6 20\n4 7 35\n5 7 20\n6 7 30\n1 7 99\n0 0\n```\n\n## 示例输出\n```\nScenario #1\nMinimum Number of Trips \u003d 5\n```\n"}}]}