odd doctor 已更新

炸桥

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
5.56%(1/18)
Description:

在这次战役中我们损失惨重,需要进行战略性撤退。为了防止追兵,我们需要把撤退途中的桥炸断。

由于弹药和人员所限,我们只能炸断一座桥。

我们撤退地图是一幅无向图,每条路连通ai,bi两座城市,路的权值w表示这条路同时能通过的军队数量。

而一座桥的定义是,如果我们炸掉这条无向路,就能把我们和敌军完全分开,那么这条路就是桥。

根据经验,桥的权值越大表示这个桥越大,也就是这个桥越难修。现在我们只有你这一位炸弹专家,请问我们应该炸断哪座桥?

Input:

有多组测试数据。

第一行有两个整数n,m,分表表示n座城市和m条路(2<=n<=1000,1<=m<=200000)

接下来m行,每行有三个整数ai,bi,w,含义如描述所述。

Output:

按输入的顺序输出这座桥。如果有多座桥符合答案,请输出输入顺序在前的桥。

如果不存在桥或者我们和敌军原本就是完全分开的,请输出-1。

Sample Input:
4 4
3 4 1
2 3 3
4 2 5
2 1 4
Sample Output:
2 1

Submit