1350. 战争传说

【题目描述】

在遥远的地方有一个大海。

在大海上有N个小岛。

有一些有向的桥将这些小岛连接起来。

有一个叫做“壹号国”的国家位于1号小岛上。

还有一个叫做“其它国”的国家位于N号小岛上。

“壹号国”起兵进攻“其它国”，挑起了一场战争。

“其它国”想到了一个策略，想通过破坏一些桥，斩断1号小岛同N号小岛的联系，借此来实现防守。

破坏不同的桥有不同的代价。

“其它国”有个大仙儿，能掐会算，他能算出来为实现防守策略而拆桥所需要的最小代价。

“壹号国”有一个建筑队，能把一个桥重建并使其坚不可摧，他们也能在2～N-1号小岛任意两个小岛间新建一个坚不可摧的桥。

但是在“其它国”开始拆桥之前，“壹号国”没有足够的时间了，所以它只能新建一个桥或者将一个已经存在的桥重建。

现在问题是：“壹号国”想让“其它国”拆桥的最小代价最大化，那么那个可能的最大解是多少呢？

【输入格式】

输入文件有多组测试数据。

文件的第一行有一个整数，即接下来测试数据的个数,不超过100组。

对于每个测试数据，第一行有两个数：N，M，（4<=N<=100;

0<=M<=N*(N-1)/2）,分别表示小岛的个数及桥的个数。

接下来有M行，每一行有三个整数a,b,c，（1<=a,b<=N;

1<=c<=10000），表示有一个有向的桥从小岛a连向小岛b，拆除它的代价为c。

数据保证没有重边。

【输出格式】

对于每个测试数据，输出只有一行，即上述可能的最大解。

【样例输入】

4
4 0
4 2
1 2 2
3 4 2
4 3
1 2 1
2 3 1
3 4 10
4 3
1 2 5
2 3 2
3 4 3

【样例输出】

0
2
1
3

【提示】

在此键入。

【来源】

在此键入。