描述

背景

雨果·重型（Hugo Heavy）很高兴。在巨型运输机（Cargolifter）项目失败后，他现在可以拓展业务了。但他需要一个聪明的人来告诉他，从他的客户建造巨型钢铁起重机的地方，到需要起重机的地方，是否真的存在一条所有街道都能承受其重量的路线。

幸运的是，他已经有了一份城市规划图，上面标注了所有的街道、桥梁以及所有街道允许的载重量。不幸的是，他不知道如何找到最大载重量，以便告诉他的客户起重机可以造多重。但你肯定知道。

问题

你会得到城市规划图，通过交叉路口之间的街道（带有重量限制）来描述，这些交叉路口从1到n编号。你的任务是找到从交叉路口1（雨果的位置）到交叉路口n（客户的位置）能够运输的最大重量。你可以假设至少存在一条路径。所有街道都可以双向通行。

输入

第一行包含场景的数量（城市规划图的数量）。对于每个城市，在第一行给出交叉路口的数量n（1 <= n <= 1000）和街道的数量m。接下来的m行包含三个整数组成的三元组，指定街道的起始交叉路口、结束交叉路口以及最大允许重量，该重量为正数且不大于1000000。每对交叉路口之间最多只有一条街道。

输出

每个场景的输出都以一行 “Scenario #i:” 开头，其中i是从1开始的场景编号。然后打印一行，包含雨果可以运输给客户的最大允许重量。在场景输出的最后添加一个空行。

输入数据 1

1
3 3
1 2 3
1 3 4
2 3 5

输出数据 1

Scenario #1:
4

来源 2004年德国达姆施塔特工业大学编程竞赛