Description

Hugo需要将巨型起重机从工厂运输到他的客户所在的地方，经过的所有街道都必须能承受起重机的重量。他已经有了所有街道及其承重的城市规划。不幸的是，他不知道如何找到街道的最大承重能力，以将起重机可以有多重告诉他的客户。

街道（具有重量限制）之间的交叉点编号为$1～n$ 。找到从$1$号（Hugo的地方）到 $n$ 号（客户的地方）可以运输的最大重量。假设至少有一条路径，所有街道都是双向的。

Format

Input

第1行包含测试用例数量。每个测试用例的第1行都包含n $（1≤n ≤1000）$和 $m$ ，分别表示街道交叉口的数量和街道的数量。以下 $m$ 行，每行都包含$3$个整数（正数且不大于$10^6$ ），分别表示街道的开始、结束和承重。在每对交叉点之间最多有一条街道。

Output

对每个测试用例，输出都以包含“Scenario #i :”的行开 头，其中i 是从1开始的测试用例编号。

然后单行输出可以运输给客户的最大承重。在测试用例之间有一个空行。

Samples

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

Scenario #1:
4