战争传说

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file war.in Output file war.out

【题目描述】

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

在大海上有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

【提示】

在此键入。

【来源】

在此键入。