CF700C Break Up

贝尔兰又一次陷入了艰难时期！许多城镇之间的紧张局势甚至可能引发内战。 在 Reberland 有 $n$ 个城镇，其中一些城镇之间由双向道路连接。并不保证通过这些道路可以从任意一个城镇到达另一个城镇。 城镇 $s$ 和 $t$ 宣布彻底断绝任何关系，并打算通过关闭道路来排除两地之间的任何通行可能。现在或许需要关闭几条道路，使得从 $s$ 到 $t$ 已经无法行走。每个城镇同意为封路花费资金，但每个城镇最多同意关闭一条道路，因此总共关闭的道路不会超过两条。 请帮他们找出一组不超过两条的道路，在关闭这几条道路后，无法通过道路从 $s$ 到 $t$。对于每条道路，已给出关闭所需的预算。在所有可能的方案中，找出总预算最小的那一组道路。

输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 1000$，$0 \le m \le 30000$）——贝尔兰的城镇数和公路数。 第二行包含两个整数 $s$ 和 $t$（$1 \le s, t \le n$，$s \ne t$）——断绝关系的两个城镇的编号。 接下来 $m$ 行，每行包含三个整数 $x_i$、$y_i$ 和 $w_i$（$1 \le x_i, y_i \le n$，$1 \le w_i \le 10^9$），表示第 $i$ 条道路连接的两个城镇的编号，以及关闭这条道路所需的预算。 所有道路均为双向道路。允许一对城镇之间有多条道路。允许存在连接自身的道路。

第一行输出断绝 $s$ 和 $t$ 之间道路所需的最小预算，如果关闭的道路最多为两条。 第二行输出需要关闭的道路条数 $c$（$0 \le c \le 2$）。 第三行输出按任意顺序输出 $c$ 个整数，分别为要关闭道路的编号，编号按照输入的顺序从 $1$ 到 $m$。 如果无法通过关闭至多两条道路使 $s$ 和 $t$ 不连通，则输出一行 $-1$。 如有多组方案，输出任意一组均可。

由 ChatGPT 5 翻译