Problem G
Ortest Path

Consider an undirected graph where each edge $e$ is labelled by a truth value $b(e)\in \{ 0,1\} $, where we interpret $0$ as false and $1$ as true. An ortest path is a simple path whose disjunction (Boolean “or”, $\vee $) is $1$, i.e., where $b(v_1v_2) \vee \dots \vee b(v_{k-1}v_ k) = 1$. Recall that a simple path from $v_1$ to $v_ k$ in a graph is a sequence of adjacent unique vertices $v_1$,$\ldots $, $v_ k$. Also recall that $0\vee 0 = 0$ and $0\vee 1 = 1\vee 0= 1\vee 1= 1$.

Given vertices $s$ and $t$, find an ortest path from $s$ to $t$. Below are three examples. Except for $G_1$, the drawings omit vertex indices and edge labels $0$ for readability. An ortest path from $s$ to $t$ is emphasized; note that $G_3$ contains many ortest paths.

Not every graph contains an ortest path, here are three small examples:

Input

The input starts with a line containing four non-negative integers: the number $n \in \{ 2,\ldots , 10\, 000\} $ of vertices, the number $m \in \{ 1,\ldots , 30\, 000\} $ of edges, and the indices of $s$ and $t$ with $s\neq t$. Vertices are indexed from $\{ 0, \ldots , n-1\} $. Then follow $m$ lines, each consisting of three integers $u$, $v$, and $b$, where $0 \leq u < v < n$ and $b\in \{ 0,1\} $, meaning that there is an undirected edge between $u$ and $v$ labeled $b$. No edge appears more than once in this list.

Output

Print a sequence of vertex indices $v_1$, $\ldots $, $v_ k$ separated by whitespace, such that $v_1=s$, $v_ k= t$, no vertex appears more than once, there is an edge between $v_ i$ and $v_{i+1}$ for each $i\in \{ 0,\ldots , k-1\} $, and $b(v_1v_2) \vee \dots \vee b(v_{k-1}v_ k) = 1$. If no such path exists, print $-1$.

Scoring

There are five test groups.

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

0 1 2 3 

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

0 1 3 

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

4 3 2 1 

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

-1

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

-1

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

-1