再说一次,伯兰德也有困难时期!许多城镇的局势十分紧张,甚至有可能爆发内战。
雷伯兰有 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