Intercept

Time limit1sMemory limit256 MB

Summary

Find every station that lies on all shortest routes from s to t in a directed weighted graph.

Level: Medium7 of 10
Topics: Shortest path, Graph, Topological sort
Solved: No attempts yet

Problem

Fatima rides the subway home from KTH every day. Today Robert baked cookies and wants to surprise her by bringing them to a station somewhere along the way. Fatima does not always take the same route home, because she likes to look at the artwork inside the different stations of Stockholm. She always keeps her travel time as short as possible, so she only uses shortest routes. Tell Robert which stations he can go to and still be certain to meet Fatima.

In other words, report every station that all shortest paths from $s$ to $t$ pass through.

Input

The first line contains two integers $N$ and $M$ , the number of subway stations and the number of subway links. ( $1 \le N, M \le 100\,000$ )

Each of the next $M$ lines contains three integers $u$ , $v$ , $w$ ( $0 \le u, v < N$ , $0 < w \le 1\,000\,000\,000$ ), meaning that there is a one way link from station $u$ to station $v$ that takes $w$ seconds to complete. Different subway lines may serve the same route, so the same pair $(u, v)$ can appear more than once.

The last line contains two integers $s$ and $t$ ( $0 \le s, t < N$ ), the number of the station closest to KTH and the number of the station closest to home. Station $t$ is reachable from station $s$ .

Output

Print on one line every station number $u$ such that all shortest paths from $s$ to $t$ pass through $u$ , in increasing order. Separate the numbers with single spaces.

Examples5

Example 1

Input

Expected output

0 3

Example 2

Input

Expected output

0 3 6

Example 3
Input
```
2 1
0 1 5
0 0
```
Expected output
```
0
```

Example 4

Input

5 4
0 1 7
1 2 3
2 3 1000000000
3 4 1
0 4

Expected output

0 1 2 3 4

Example 5
Input
```
2 3
0 1 4
0 1 4
0 1 9
0 1
```
Expected output
```
0 1
```