炸桥

Grade 100 Open Time Wednesday, 17 June 2020, 10:00 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 10:00 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 10:00 PM
Input file bridge.in Output file bridge.out

【题目描述】炸桥(bridge)HDU 4738

暴力组织在海上建立了许多人工岛,人工岛之间有桥相连,如果这些人工岛构成的无向图变成了连通图,那么处理起来会非常麻烦。小光一行打算用遥控机器人毁掉一座桥,使得一个或多个人工岛彼此不能连通。由于每座桥都有一定数量的士兵在守护,所以遥控机器人的数量不能少于该桥上的士兵人数。试编程输出需要派出遥控机器人的最少数量。

【输入格式】

输入有多组测试数据,但不超过12组。

每组数据第一行有两个整数N和M,表示有N个岛和M座桥,岛的编号范围为1~N ( 2≤N≤1 000,0<M≤N2 )。

随后M行,每行三个整数U,V和W,表示U岛和V岛的守护士兵人数为W (U≠V,0≤W≤10 000)。

全部数据结束以两个0表示。

【输出格式】

每组数据输出派出遥控机器人的最少数量,如果不能成功,输出“-1”。

【输入样例】

3 3

1 2 7

2 3 4

3 1 4

3 2

1 2 7

2 3 4

0 0

【输出样例】

-1

4