問題文

太郎君の住んでいる地域には地下鉄の駅が$N$個あり、$0$から$N-1$までの番号が振られています。
駅と駅は路線で結ばれており、それぞれの路線について移動時間が決まっています。

急ぎの用事がある太郎君は駅$S$から駅$G$までの最短経路を気にしています。
駅$S$から駅$G$までの最短経路を出力するプログラムを書いてください。
ただし、そのような経路は複数考えられる場合があるので、最短経路のうち辞書順最小のものを出力してください。

ここで最短経路とは用いる路線の移動時間の和が最小となる経路のことです。乗り換えの時間などは考慮する必要はありません。経路は、出発する駅と目的の駅を含みます。
ある経路$P$が経路$Q$よりも辞書順で小さいというのは、経路上の駅をそれぞれ$(p_1,p_2,\dots ,p_k)$と$(q_1,q_2,\dots ,q_l)$と表した時、ある$j$が存在して、$i=1,2,\dots ,j-1$について$p_i=q_i$かつ$p_j<q_j$となることです。

入力

$N$ $M$ $S$ $G$
$a_1$ $b_1$ $c_1$
$\dots$
$a_M$ $b_M$ $c_M$

$1$行目に駅の数を表す$N$、路線の本数を表す$M$、出発する駅$S$、目的地の駅$G$がスペース区切りで与えられます。
続く$M$行は路線の情報で、駅$a_i$と駅$b_i$を結ぶ路線の移動時間は$c_i$であることを表します。 路線は駅$a_i$から駅$b_i$の向きへも、駅$b_i$から駅$a_i$の向きへも利用できます。

$2\le N\le 200$
$N-1\le M\le N(N-1)/2$
$1\le c_i\le {10}^4$
$0\le S,G,a_i,b_i\le N-1$
$S\ne G$
$a_i\ne b_i$
ある駅の組を直接結ぶ路線は高々$1$つである。
駅$S$から駅$G$に向かう経路は必ず存在する。

出力

$S$ $v_2$ $v_3$ $\dots$ $v_{k-1}$ $G$    

$1$行に最短経路のうち辞書順最小のものを出力してください。
経路は、通る駅を順番にスペース区切りで並べてください。出発する駅と目的地の駅を含みます。
最後に改行してください。

サンプル

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

0 2 1 3

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

0 2 3

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

0 1 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

4 1 3 5 0 6