005 - スニーカーマン

問題

Mr.Three-Islandは彼が保持しているMPを消費して「ル○ラ」と呼ばれているワープ魔法を使うことができる。
ワープ魔法はワープしたいところに魔法陣をあらかじめ書いておく必要があり、魔法陣には0からN−1までの番号が振られている。
1つの魔法陣はいくつかの魔法陣にワープできる。
その魔法陣がどこの魔法陣にワープするかは決まっていて、それぞれのワープポイントに移動するMPは異なる。

ある日、Mr.Three-Islandは自身の一番お気に入りのスニーカーを片方だけ魔法陣Gの近くに忘れてきてしまった。
ヤベ、マジでヤベェと思った彼は最寄りの魔法陣Sから魔法陣Gまでスニーカーを取りに行くことにした。

最近だらけているMr.Three-Islandは「ベホ○ミ」（回復魔法）にMPを回したいためMPをたくさん消費したくない。
そのとき、魔法陣Sから魔法陣Gまで最もMPを消費しない経路を求めてください。
ただし、そのような経路は複数考えられる場合があるので、最もMPを消費しない経路のうち辞書順で最小のものを出力してください。

経路は、出発する魔法陣Sと目的の魔法陣Gを含む。
ある経路Pが経路Qよりも辞書順で小さいというのは、経路上の駅をそれぞれ(p1,p2,…,pk)と(q1,q2,…,qlと表した時、あるjが存在して、i=1,2,…,j−1についてpi=qiかつpj＜qjとなることです。

入力

N M S G
a1 b1 c1
…
aM bM cM

1行目に魔法陣の数を表すN、魔法陣どうしの本数を表すM、出発する魔法陣S、目的地の魔法陣Gがスペース区切りで与えられます。
続くM行はMPの情報で、魔法陣aiと魔法陣bi間の「ル○ラ」のMP消費量はciであることを表す。
魔法陣は魔法陣aiから魔法陣biの向きへも、魔法陣biから魔法陣aiの向きへも利用できる。

制約

2 ≤ N ≤ 1000
N−1 ≤ M ≤ N(N−1)/2
1≤ ci ≤ 10000
0≤ S, G, ai, bi ≤ N−1
S ≠ G
ai ≠ bi

魔法陣Sから魔法陣Gに向かう経路は必ず存在する。

出力

S v2 v3 … vk−1 G

1行に最もMP消費の少ない経路のうち辞書順最小のものを出力してください。
経路は、通る魔法陣を順番にスペース区切りで並べてください。出発する魔法陣と目的地の魔法陣を含む。
最後に改行してください。

入力例1

4 3 0 3
0 2 100
2 1 200
1 3 300

出力例1

0 2 1 3

解説

魔法陣0から魔法陣3に向かう経路は(0,2,1,3)の1つしかないため、これを出力する。

入力例2

4 4 0 3
0 2 100
2 3 100
0 1 100
1 3 100

出力例2

0 1 3

解説

魔法陣0から魔法3に向かう経路は(0,2,3)と(0,1,3)の2つである。
2つの経路の消費MPは等しいが、(0,2,3)より(0,1,3)の方が辞書順で小さいため、経路(0,1,3)を出力する。

入力例3

8 28 4 6
1 4 15
4 5 2457
1 6 8234
0 7 109
5 2 6669
0 5 31
2 6 1
0 3 2896
0 4 1493
7 5 78
5 6 96
2 7 7486
0 2 66
7 6 4776
4 2 3820
2 3 8843
4 7 8276
3 1 67
1 5 4053
1 0 912
3 4 82
6 3 3165
5 3 81
1 2 2948
4 6 3164
3 7 3
1 7 70
0 6 65

出力例3

4 1 3 5 0 6