2104. 小强过桥

单点时限: 5.0 sec

内存限制: 256 MB

给出一个无向图,N 个结点,M 条边。我要从 s 出发到 t, 每一条边是一座不稳定的桥,如果小强带的货物重量超过了桥的承重,小强就会掉到河里。小强最多能带多少货物呢?

输入格式

多组数据。每组数据以 N M(1<= N <= 100000,1<= M <= 1000000) 开始,下面 M 行,每行有三个整数,x y w(1<=x<=N,1<=y<=N,1<=w<=<=2,000,000,000),表示桥的起点、终点和承重。最后一行包含 s t 两个整数。

输出格式

对于每组数据,输出最大的重量。

样例

Input
6 6
1 5 2000
2 4 5000
2 5 3300
3 4 2400
3 6 2200
4 6 6000
3 5
Output
2400

26 人解决,46 人已尝试。

54 份提交通过,共有 221 份提交。

5.5 EMB 奖励。

创建: 12 年,4 月前.

修改: 3 年前.

最后提交: 5 天,22 小时前.

来源: N/A

题目标签