说明

题目背景

（背景里面的都是废话，想直接做题可以从题目描述开始看）

注意：题目背景非真实历史

1937 年 埃及亚历山大港

在上次大战中，有些事情有了变化，例如德国和奥地利，他们彻底击垮了法国，意大利和俄罗斯；但是有些事情是没有变的，那就是同在同盟国内的奥斯曼土耳其。

英国的中东远征军依然和现实中一样联合阿拉伯起义势力在中东高歌猛进，甚至一度攻至安纳托利亚高原，奥斯曼帝国差点就要成为同盟国中唯一的战败成员了。

最后，奥斯曼帝国迎来了苦涩的和平。虽然他好不容易在德国的帮助下镇压了阿拉伯地区的叛乱，却永远失去了埃及，包括西奈半岛和苏伊士运河的控制权。

1925 年，英国发生革命，埃及苏丹国从此脱离了殖民者走向独立。新生的埃及从一开始对奥斯曼就带着沙文主义立场——埃及希望有朝一日彻底击垮奥斯曼帝国这个旧秩序的残留者，它已经欺压阿拉伯民族太长时间了。

1936 年巴黎召开了第三国际大会，埃及亦派遣代表参加。大会结束后不久，英国船只再次抵达了亚历山大港，英国军人也再次来到了埃及。然而这次他们不再代表国王和殖民者，而是不列颠联盟为了帮助埃及派遣了一批规模庞大的军事顾问团。

随后到来的，还有产自法兰西公社的新式坦克与枪械，和产自不列颠联盟的新式飞机。

题目描述 

埃及苏丹国境内拥有一个还算具备一定规模的铁路网。 

埃及总共有 n(1≤n≤1000) 座城市和 m 条双向连通的铁路，每条铁路都有一个承载货物的重量上限。 

来自第三国际的各种货物主要是从亚历山大港（ 1 号城市）输送到苏伊士（ n 号城市），那里离和土耳其的边界并不算太远。 苏丹想选择一条路线专门用于输送这些货物。他想知道这条路线一次性最多能送多少货。

输入格式

第一行一个整数 T，为数据的组数（不超过 5）。 

对于每组数据，第一行有两个数 n,m。 往后 m 行每行三个数，表示铁路线的两端和这条铁路承载货物的重量上限，这个上限不超过 10^6 。

输入保证 n 座城市两两之间都能通过铁路线连通，且没有任意两座城市间有多于一条直接连通的铁路线。

输出格式

对于第 i 组数据，输出两行，其中第一行的格式是：Scenario # i。

第二行是从 1 号城市到 n 号城市一次性最多能运货的重量。

样例

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

Scenario #1:
4

提示

对于样例，苏丹可以直接选择 1→3 这条铁路作为运输线，一次性运送货物的重量最多为 4。