사전순으로 가장 작은 경로

$N$개의 정점과 $M$개의 간선으로 이루어진 방향 그래프 $G$가 있다. 각 정점에는 $1$부터 $N$까지의 번호가, 각 간선에는 $1$부터 $M$까지의 번호가 붙어 있다. 각 $i$ ($1 \le i \le M$)에 대해, 간선 $i$는 정점 $u\_i$에서 정점 $v\_i$로 향하며 고유한 색 $c\_i$를 가진다.

경로(walk)는 간선의 나열 $e\_1, e\_2, \cdots, e\_{l}$로서, 각 $1 \le k < l$에 대해 $v\_{e\_k}$(간선 $e\_k$의 끝)가 $u\_{e\_{k+1}}$(간선 $e\_{k+1}$의 시작)과 같다. 경로 $e\_1, e\_2, \cdots, e\_l$은 정점 $u\_{e\_1}$에서 시작해 정점 $v\_{e\_l}$에서 끝난다고 말한다. 같은 간선이 경로에 여러 번 나타날 수 있다.

경로 $e\_1, e\_2, \cdots, e\_l$의 색 수열은 $c\_{e\_1}, c\_{e\_2}, \cdots, c\_{e\_l}$로 정의한다.

$G$에서 정점 $S$에서 정점 $T$로 가는, 길이가 $10^{100}$ 이하인 모든 경로의 색 수열을 생각하자. 그중 사전순으로 가장 작은 수열을 찾는 프로그램을 작성하시오.

첫째 줄에 네 정수 $N$, $M$, $S$, $T$가 공백으로 구분되어 주어진다 ($1 \le N \le 100\,000$, $0 \le M \le 300\,000$, $1 \le S \le N$, $1 \le T \le N$, $S \neq T$).

이어서 $M$개의 줄이 주어진다. $i$ ($1 \le i \le M$)번째 줄에는 세 정수 $u\_i$, $v\_i$, $c\_i$가 공백으로 구분되어 주어진다 ($1 \le u\_i, v\_i \le N$, $u\_i \neq v\_i$, $1 \le c\_i \le 10^{9}$). 이는 정점 $u\_i$에서 정점 $v\_i$로 향하는 색 $c\_i$의 간선을 나타낸다.

그래프에는 중복 간선이나 자기 자신으로 향하는 간선이 없으며, 각 간선은 고유한 색을 가진다. 즉, 임의의 $1 \le i < j \le M$에 대해 $c\_i \neq c\_j$이고 $(u\_i,\ v\_i) \neq (u\_j,\ v\_j)$이다.

정점 $S$에서 정점 $T$로 가는 경로가 없으면 "IMPOSSIBLE"을 출력한다. (따옴표 제외)

그렇지 않다면, $a\_1, a\_2, \cdots, a\_l$을 정점 $S$에서 정점 $T$로 가는, 길이가 $10^{100}$ 이하인 모든 경로의 색 수열 중 사전순으로 가장 작은 수열이라 하자.

• $l \le 10^{6}$이면 첫째 줄에 $a\_1, a\_2, \cdots, a\_l$을 출력한다. 각 정수 사이에는 공백을 하나 둔다.
• $l > 10^{6}$이면 "TOO LONG"을 출력한다. (따옴표 제외)

수열 $p\_1, p\_2, \cdots, p\_{n}$이 다른 수열 $q\_1, q\_2, \cdots, q\_{m}$보다 사전순으로 작다는 것은 다음 중 하나가 성립한다는 뜻이다:

• $p\_1 = q\_1$, $p\_2 = q\_2$, $\cdots$, $p\_{j} = q\_{j}$이고 $p\_{j+1} < q\_{j+1}$인 $j$ ($0 \le j < \min(n, m)$)가 유일하게 존재한다.
• $n < m$이고 $p\_1 = q\_1$, $p\_2 = q\_2$, $\cdots$, $p\_n = q\_n$이다. 즉, $p$가 $q$의 진부분 접두사이다.