가로채기

파티마는 매일 지하철을 타고 KTH에서 집으로 간다. 오늘 로버트는 쿠키를 구워 중간에 있는 역으로 가져가서 파티마를 놀래 주기로 했다. 파티마는 스톡홀름의 여러 역에 있는 예술 작품을 구경하는 것을 좋아해서 늘 같은 경로로 집에 가지는 않는다. 대신 이동 시간은 언제나 최소로 유지하므로 최단 경로만 이용한다. 로버트가 파티마를 반드시 만나려면 어느 역으로 가야 하는지 알려 주자.

다시 말해 $s$에서 $t$로 가는 모든 최단 경로가 빠짐없이 지나는 역을 모두 구한다.

첫째 줄에 지하철 역의 개수 $N$과 구간의 개수 $M$이 주어진다. ($1 \le N, M \le 100\,000$)

다음 $M$개 줄에는 각각 세 정수 $u$, $v$, $w$가 주어진다. ($0 \le u, v < N$, $0 < w \le 1\,000\,000\,000$) 이는 역 $u$에서 역 $v$로 가는 일방통행 구간이 있고 지나는 데 $w$초가 걸린다는 뜻이다. 서로 다른 노선이 같은 구간을 운행하기도 하므로 같은 $(u, v)$ 쌍이 여러 번 주어질 수 있다.

마지막 줄에 두 정수 $s$와 $t$가 주어진다. ($0 \le s, t < N$) $s$는 KTH에서 가장 가까운 역, $t$는 집에서 가장 가까운 역의 번호다. $s$에서 $t$로 가는 경로는 반드시 존재한다.

$s$에서 $t$로 가는 모든 최단 경로가 지나는 역의 번호 $u$를 증가하는 순서로 한 줄에 출력한다. 번호는 공백 하나로 구분한다.