2056 - 遅刻挽回中のKamba君

問題

ある日、Kamba君は大切な予定がありましたが、寝坊してしまい遅刻しそうになっています。目的地までは遠く、移動手段は電車しかありません。さらに、約束の時間まで残された時間は $X$ 分しかありません。
駅の数、隣接する駅の数、残り時間、および隣接する駅同士の情報（駅間の移動時間）をもとに、始点の駅から目的地の駅まで、$X$ 分以内に到達できる最短ルートが存在するかを判定し、存在する場合にはそのルートを、しない場合には $-1$ を出力してください。
ただし、全ての駅は相互に連結されており、最短経路は必ず一意に定まるように設計されています。

入力

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

$N$ $M$ $X$
$S$ $G$
$U_1$ $V_1$ $T_1$
$U_2$ $V_2$ $T_2$
$:$
$:$
$U_M$ $V_M$ $T_M$

1行目に駅の総数を表す数 $N$ 、隣接する駅の総数 $M$ 、残り時間 $X$ 分が空白区切りで与えられる。
2行目にスタート地点 $S$ とゴール地点 $G$ が与えられる。
3行目以降、隣接する駅 $U$ から駅 $V$ へ移動にかかる時間 $T$ 分が与えられる。

出力

$X$ 分以内に目的地へ到達できる場合：最短ルートの始点から目的地までの駅の並びを改行区切りで出力すること。
$X$ 分以内に目的地へ到達できない場合： $-1$ を出力すること。

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

制約

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

• $2 \leq N \leq 7.4 \times 10^3$
• $1 \leq M \leq 7.4 \times 10^4$
• $1 \leq X \leq 7.4 \times 10^8$
• $1 \leq S, G \leq N$ かつ $S \ne G$
• $1 \leq U_i, V_i \leq N$ $(1\leq i \leq N)$
• 駅を表す番号 $(U_i, V_i)$ の組は重複せず、$U_i \ne V_i$ である。 $(1\leq i \leq N)$
• $1 \leq T_i \leq 10^8$
• 各隣接する駅間の時間は全て異なる。
• 無向グラフであり、常に連結している。
• 入力は全て整数である。

入出力例

入力例1

6 7 20
1 6
1 2 3
2 3 4
3 1 5
2 4 3
4 5 2
5 6 3
6 3 8

出力例1

1
2
4
5
6

入力例2

5 5 10
1 5
1 2 4
2 3 4
3 4 4
4 5 5
2 5 9

出力例2

-1

入力例3

5 10 15
1 5
1 2 3
2 3 4
3 1 5
1 4 6
2 4 2
3 5 8
4 5 3
2 5 7
3 4 6
1 5 9

出力例2

1
2
4
5