图的割边问题， 使用 tarjan 算法求出
本题要点：
1、若图本身不连通，则先输出 0
2、若得到的割边的最大值为0， 应该输出1。因为至少派一个人去炸桥。
3、 关键的是 tarjan 算法:
dfn[MaxN], 表示递归访问的时间戳
low[MaxN]数组，
low[x] 表示能够通过不在搜索树上的一条边，到达子树 subtree(x) 的节点的 时间戳最小的节点；
4、 tarjan，只需要判定 low[v] > dfn[u] 即可(u为父，v为子)
解释：如果子节点在不走原路情况下到不了父节点或父节点之前的点，那么子节点只能走原路回到父节点及之前节点，
原路为必经之路，断掉就会产生新的个联通块，符合割边定义。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 1010;
const int MaxM = 1000010;
int n, m, tot;
int num; //记录递归时间戳
int head[MaxN], ver[MaxM], Next[MaxM], edge[MaxM];
int dfn[MaxN], low[MaxN];
bool bridge[MaxM]; // 记录这个边是否是割边void add(int x, int y, int z)
{
ver[++tot] = y, Next[tot] = head[x], head[x] = tot, edge[tot] = z;
}void tarjan(int x, int in_edge)
{
dfn[x] = low[x] = ++num;for(int i = head[x]; i; i = Next[i]){
int y = ver[i];if(!dfn[y]){
tarjan(y, i);low[x] = min(low[x], low[y]);if(low[y] > dfn[x]){
bridge[i] = bridge[i ^ 1] = true; }}else if(i != (in_edge ^ 1)){
low[x] = min(low[x], dfn[y]);}}
}int main()
{
while(scanf("%d%d", &n, &m) != EOF && n){
memset(head, 0, sizeof head);memset(Next, 0, sizeof Next);memset(dfn, 0, sizeof dfn);memset(low, 0, sizeof low);memset(bridge, false, sizeof bridge);tot = 1;int x, y, z;for(int i = 1; i <= m; ++i){
scanf("%d%d%d", &x, &y, &z);add(x, y, z);add(y, x, z);}int block = 0; //连通块for(int i = 1; i <= n; ++i){
if(!dfn[i]) {
++block;tarjan(i, 0);}}if(block > 1){
printf("0\n");continue;}int ans = 0x3f3f3f3f, cnt = 0;for(int i = 2; i < tot; i += 2){
if(bridge[i]){
++cnt;ans = min(ans, edge[i]);}}if(!cnt){
printf("-1\n");}else{
if(!ans){
++ans;}printf("%d\n", ans);}}return 0;
}/* 3 3 1 2 7 2 3 4 3 1 4 3 2 1 2 7 2 3 4 0 0 *//* -1 4 */