1814 - 最長経路問題

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / Writer woody_1227 / x 11 / 統計 /

TLE
1sec
MLE
64MB
得点
100

問題

HOJ市にはHOJ鉄道があり、黒色の電車(通称：黒電)が走っています。
HOJ鉄道には、$N$個の駅と2つの駅をつなぐ$M$本の線路があります。
線路$i$は、駅$A_{i}$と駅$B_{i}$をつなぎ、距離は$C_{i}$です。

HOJ鉄道では、利用者の利便性向上のため、考えられる経路それぞれを通る電車を運行しています。
HOJ鉄道では、複数の路線を運営していることはありますが、環状線を運営していることはありません。

さて、HOJ鉄道では、料金形態が特殊な「区間料金切符」を販売しています。
この切符では、通った駅の数や乗車した距離に関わらず、乗車駅と降車駅の間の最短距離によって、金額が決定されます。
ただし、この切符を利用して乗車する場合、同じ駅を複数回通過することはできません。
また、駅$X$から駅$Y$まで移動する電車が無い場合、そのような切符は販売されません。

鉄道好きのあなたは、この切符1枚を使って、できるだけ長く電車に乗車していたいと考えました。

駅$S$から駅$G$まで、この切符を利用して乗車するとき、料金はいくらになりますか？
また、駅$S$から駅$G$までの最長経路を1つ求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $S$ $G$
$A_{1}$ $B_{1}$ $C_{1}$
$A_{2}$ $B_{2}$ $C_{2}$
 :   :   :
$A_{M}$ $B_{M}$ $C_{M}$

出力

1行目に駅$S$から駅$G$まで「区間料金切符」を利用して乗車するときにかかる料金を出力してください。
2行目に駅$S$から駅$G$までの最長経路において、通過する駅を通過する順で空白区切りで出力してください。
なお、そのような経路が複数考えられる場合はどれを出力しても構いません。

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • $1 \leq N \leq 10^{5}$
  • $0 \leq M \lt N$
  • $1 \leq S, G \leq N$
  • $1 \leq A_{i} \leq N$
  • $1 \leq B_{i} \leq N$
  • $1 \leq C_{i} \leq 10^{5}$

入出力例

入力例1

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

出力例1

10
1 2 3 4 5

駅$1$から駅$5$までの最短距離は10です。
また、考えられる駅$1$から駅$5$までの最長経路の1つは、 1 -> 2 -> 3 -> 4 -> 5 です。

入力例2

1 0 1 1

出力例2

0
1

駅が1つしかないこともあります。