Hide

Problem D
Intercept

/problems/intercept/file/statement/en/img-0001.jpg
Photo by Patrik Neckman

Fatima commutes from KTH to home by subway every day. Today Robert decided to surprise Fatima by baking cookies and bringing them to an intermediate station. Fatima does not always take the same route home, because she loves to admire the artwork inside different stations in Stockholm. However, she always optimizes her travel by taking the shortest route. Can you tell Robert which station he should go to in order to surely intercept Fatima?

Input

The first line contains two integers $N$ and $M$, $1 \leq N,M \leq 100\, 000$, where $N$ is the number of subway stations and $M$ is the number of subway links. $M$ lines follow, each with three integers $u$, $v$, $w$, $0 \leq u,v < N$, $0 < w \leq 1\, 000\, 000\, 000$, meaning that there is a one-way link from $u$ to $v$ that takes $w$ seconds to complete. Note that different subway lines may serve the same route.

The last line contains two integers $s$ and $t$, $0 \leq s,t < N$ the number of the station closest to KTH and closest to home, respectively. It is possible to reach $t$ from $s$.

Output

A space separated list of all the station numbers $u$ such that all shortest paths from $s$ to $t$ pass through $u$, in increasing order.

Sample Input 1 Sample Output 1
4 4
0 1 100
0 2 100
1 3 100
2 3 100
0 3
0 3
Sample Input 2 Sample Output 2
7 8
0 1 100
0 2 100
1 3 100
2 3 100
3 4 100
3 5 100
4 6 100
5 6 100
0 6
0 3 6

Please log in to submit a solution to this problem

Log in