← 返回题目列表

Codeforces · 700/C

C. 分手

中文机器翻译题面 查看原题

再说一次,伯兰德也有困难时期!许多城镇的局势十分紧张,甚至有可能爆发内战。

雷伯兰有 n 个城镇,其中一些城镇由双向道路连接。不保证可以使用这些道路从任何其他城镇到达一个城镇。

Towns 和 t 宣布最终断绝任何关系,并打算排除他们之间通过道路移动的可能性。现在可能需要关闭几条道路,以便无法通过道路从 s 移动到 t。各镇同意花钱封闭道路不超过一条,因此封闭道路总数不超过两条。

帮助他们找到一组不超过两条道路,使得关闭这些道路后 s 和 t 之间就没有路了。对每条道路关闭所需的预算进行了估算。在所有组中,发现关闭一组道路的总预算最小。

输入

输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 30 000) — Berland 的城镇数量和道路数量。

第二行包含整数 s 和 t (1 ≤ s, t ≤ n, s ≠ t) - 破坏关系的城镇索引。

然后是 m 行,每行包含三个整数 xi、yi 和 wi (1 ≤ xi, yi ≤ n, 1 ≤ wi ≤ 109)——第 i 条道路所连接的城镇的索引,以及其关闭的预算。

所有道路都是双向的。允许两个城镇由多条道路连接。连接城市与自身的道路是允许的。

输出

在第一行中,如果允许关闭不超过两条道路,则打印打破 s 和 t 之间关系所需的最低预算。

在第二行中打印值 c (0 ≤ c ≤ 2) — 找到的解决方案中要关闭的道路数量。

在第三行中,以任意顺序打印 c 个从 1 到 m 的不同整数——封闭道路的索引。考虑道路按照它们在输入中出现的顺序从 1 到 m 进行编号。

如果不可能通过删除不超过 2 条道路来使城镇 s 和 t 断开连接,则输出应包含单行 -1。

如果有多个可能的答案,您可以打印其中任何一个。

示例

输入 #1

6 7
1 6
2 1 6
2 3 5
3 4 9
4 6 4
4 6 5
4 5 1
3 1 3

输出 #1

8
2
2 7

输入 #2

6 7
1 6
2 3 1
1 2 2
1 3 3
4 5 4
3 6 5
4 6 6
1 5 7

输出 #2

9
2
4 5

输入 #3

5 4
1 5
2 1 3
3 2 1
3 4 4
4 5 2

输出 #3

1
1
2

输入#4

2 3
1 2
1 2 734458840
1 2 817380027
1 2 304764803

输出#4

-1