HDU 4738

Caocao's Bridges

Description

曹操在赤壁之战中战败给了诸葛亮和周瑜。但是他不会放弃。曹操的军队仍然不擅长水上作战，因此他想了一个好主意。他在长江上造了好几个小岛，通过这些小岛，他就可以轻松战胜周瑜。同时，他也造了很多连接小岛的桥，将所有的小岛连接在一块，便可以轻松部署军队。这让周瑜无法忍受，于是，周瑜想要摧毁曹操的桥，让一部分小岛和另一部分小岛分离。但是，周瑜只剩下一个诸葛亮留下来的炸弹，所以他只能炸一座桥。同时，为了炸桥，他还必须派遣军队运送炸弹。每座桥上都有士兵把守，如果周瑜派遣的军队数量少于桥上的守卫数量，那炸桥的任务就会失败。请你算出周瑜至少需要多少士兵运送炸弹，才能完成炸桥任务。

Input

输入数据不超过12组。每组数据中，第一行是两个整数 N 和 M ，表示有 N 个小岛和 M 座桥。所有小岛从1到 N 编号。

（2 ≤ N ≤ 1000, 0 < M ≤ N ²）

以下 M 行描述 M 座桥，每行包含三个整数 U 、 V 和 W ，表示有一座桥连接了小岛 U 和小岛 V ，上面有 W 个守卫。

输入数据以 N = 0 和 M = 0 表示结束。

Output

对于每组测试数据，输出周瑜为了完成任务，最少需要派遣的士兵数量。如果周瑜无论如何都没办法成功，就输出-1。

Solution

对于一张无向图，找出它所有桥中士兵数量最少的桥（这里的“桥”，指的是图论中的桥，即去掉该边以后，原先的连通图会变成不连通）。不过如果你以为这道题有这么简单，那你就太天真了。

这道题的难点在于以下三种情况，需要特殊处理：

• 两个小岛间，可能有多座桥相连。由于只能炸一座桥，所以这两个小岛间的桥，炸哪一座都不可以。
• 如果所有小岛原来就没有全部相连（不是连通图），那么周瑜就不需要炸桥了，也就是一个士兵都不用派。
• 如果桥上的守卫为0，那么你至少需要派一个士兵把炸弹运送过去，因为炸弹是不会自己长出两条腿走路的。