가로채기

사진 촬영: Patrik Neckman

Fatima는 매일 KTH에서 집까지 지하철로 통근한다. 오늘 Robert은 쿠키를 구워 중간에 있는 역으로 가져가 Fatima를 놀라게 해 주기로 했다. Fatima는 Stockholm의 여러 역 안에 있는 미술 작품을 감상하기 좋아하기 때문에 집에 갈 때 항상 같은 경로를 이용하지는 않는다. 하지만 항상 최단 경로를 택해 이동을 최적화한다. Robert가 Fatima를 반드시 만날 수 있으려면 어느 역으로 가야 하는지 알려 줄 수 있는가?

첫 번째 줄에는 두 정수 $N$와 $M$, $1 \leq N,M \leq 100\,000$가 주어진다. 여기서 $N$은 지하철역의 수이고 $M$는 지하철 연결의 수이다. 이어지는 $M$개의 줄에는 각각 세 정수 $u$, $v$, $w$, $0 \leq u,v < N$, $0 < w \leq 1\,000\,000\,000$이 주어지며, 이는 $u$에서 $v$까지 이동하는 데 $w$초가 걸리는 단방향 연결이 있음을 의미한다. 서로 다른 지하철 노선이 같은 경로를 운행할 수도 있음에 유의하라.

마지막 줄에는 두 정수 $s$와 $t$, $0 \leq s,t < N$가 주어지며, 이들은 각각 KTH에서 가장 가까운 역과 집에서 가장 가까운 역의 번호이다. $s$에서 $t$까지 도달할 수 있다.

$s$에서 $t$까지의 모든 최단 경로가 $u$를 통과하도록 하는 모든 역 번호 $u$을 공백으로 구분하여 오름차순으로 출력한다.