描述

Big Johnsson Trucks Inc. 是一家专门制造大型卡车的公司。他们的最新型号 Godzilla V12 非常庞大，其运输能力从不受卡车自身限制，而是由行驶路径上的道路重量限制决定。

给定起点和目的地城市，你的任务是确定 Godzilla V12 的最大载重，使得在指定的两个城市之间仍存在一条可行路径。

输入

输入包含一个或多个测试用例。每个测试用例的第一行包含两个整数：城市数量 $n$（$2 \leq n \leq 200$）和道路段数量 $r$（$1 \leq r \leq 19900$）。

接下来的 $r$ 行，每行描述一条道路段，包括连接的两个城市名称和该段道路的卡车重量限制。城市名称不超过 30 个字符且不包含空格。重量限制为 $0$ 到 $10000$ 之间的整数。道路可双向通行。

每个测试用例的最后一行包含两个城市名称：起点和目的地。

输入以 $n$ 和 $r$ 均为 $0$ 结束。

输出

对于每个测试用例，输出三行：

• 第一行输出 "Scenario #x"，其中 $x$ 是测试用例编号。
• 第二行输出 "$y$ tons"，其中 $y$ 是最大可能载重。
• 第三行输出一个空行。

输入样例 1

4 3  
Karlsruhe Stuttgart 100  
Stuttgart Ulm 80  
Ulm Muenchen 120  
Karlsruhe Muenchen  
5 5  
Karlsruhe Stuttgart 100  
Stuttgart Ulm 80  
Ulm Muenchen 120  
Karlsruhe Hamburg 220  
Hamburg Muenchen 170  
Muenchen Karlsruhe  
0 0  

输出样例 1

Scenario #1  
80 tons  

Scenario #2  
170 tons  

来源
Ulm Local 1998