Problem Statement

In the area where Taro lives, there are $N$ subway stations, numbered from $0$ to $N-1$.
Stations are connected by lines, and each line has a fixed travel time.

Taro, who has an urgent errand, is concerned with the shortest path from station $S$ to station $G$.
Write a program that outputs the shortest path from station $S$ to station $G$.
However, since there may be multiple such paths, output the lexicographically smallest one among the shortest paths.

Here, a shortest path is a path that minimizes the sum of the travel times of the lines used. There is no need to consider transfer times or the like. A path includes the departure station and the destination station.
A path $P$ is lexicographically smaller than a path $Q$ if, when the stations on the paths are written as $(p_1,p_2,\dots,p_k)$ and $(q_1,q_2,\dots,q_l)$ respectively, there exists some $j$ such that $p_i = q_i$ for $i=1,2,\dots,j-1$ and $p_j < q_j$.

Input

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

Line $1$ contains, separated by spaces, $N$ representing the number of stations, $M$ representing the number of lines, the departure station $S$, and the destination station $G$.
The following $M$ lines give the information about the lines: the line connecting station $a_i$ and station $b_i$ has travel time $c_i$. A line can be used both in the direction from station $a_i$ to station $b_i$ and in the direction from station $b_i$ to station $a_i$.

$2 \leq N \leq 200$
$N - 1 \leq M \leq N(N-1)/2$
$1 \leq c_i \leq 10^4$
$0 \leq S,G,a_i,b_i \leq N - 1$
$S \neq G$
$a_i \neq b_i$
At most $1$ line directly connects any given pair of stations.
A path from station $S$ to station $G$ always exists.

Output

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

Output the lexicographically smallest of the shortest paths on $1$ line.
Output the path by listing the stations it passes through in order, separated by spaces. It includes the departure station and the destination station.
Print a newline at the end.

Sample

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