Problem C
Esports on my Mind

The finals in the Striker-Count competition are finally starting. All the members of ICPS have arrived and the pizza is served. Atli decided to watch the finals despite not being familiar with Striker-Count. So Atli gets Bergur to explain the rules to him.

In Striker-Count two teams of five compete. One of the teams is called the blue team and the other is the yellow team. The teams then switch colors at halftime. The team that wins the game gets a point, and the first team to two point wins the match. Each match is played on a different map. There are two bomb sites on each map, which the blue team has to defend from the yellow team. The goal of the yellow team is to plant a bomb on the bomb sites. The bomb takes $40$ seconds to explode, during which the yellow team has to make sure the blue team doesn’t defuse the bomb. The yellow team gets a round win if the bomb successfully explodes. If one team successfully eliminates the entirety of the other team it wins the round. Finally, the yellow team loses if they don’t plant the bomb or eliminate the blue team in two minutes. The first team to win $16$ round wins the map and halftime is after $15$ rounds. If the final score is $15:15$, there is overtime. Atli quickly realizes that the players run to the same locations at the start of each round. Bergur explains to him that the players have to hurry up to get to these locations because it takes the teams almost the same time to get there. Bergur calls these locations contact points. However, Atli notices that it doesn’t always take the same time to get to a location. Bergur tells him that sometimes the players spawn in a more favourable spot, some players are better at the movement mechanics in the game, and your base movement speed depends on which weapon you are carrying. Atli therefore thinks it makes more sense to define possible contact points. Each map can be described as a directed, weighted graph. The existence of an edge from $u$ to $v$ with weight $w$ implies a path on the map from point $u$ to $v$ that takes on average $w$ time to traverse. Each edge also has a deviance $\sigma _ e$. If the weight of $e$ is $w$ it takes at least $w - \sigma _ e$ time to traverse the path and at most $w + \sigma _ e$. Atli then defines a point on the map as a possible contact point if there exists $d_ e \in [-\sigma _ e, \sigma _ e]$ for each edge $e$ such that the point becomes a contact point in the graph with precisely the weight $w_ e + d_ e$ for edge $e$. An edge is a contact point in a graph if the shortest paths from each team’s starting points to that point are equal. Which points are possible contact points.

The graph from sample $3$

Input

The first line of the input includes two integer, $n$ and $m$ with $1 \leq n, m \leq 10^5$. These integers represent the number of points on the map and the number of paths, respectively. The next line on the input includes two integers $b$ and $g$, with $1 \leq b, g \leq n$. The number $b$ gives the starting point of the blue team and $g$ gives the starting point of the yellow team. It is guaranteed that $b \neq g$. The next $m$ lines include four integers $u, v, w, \sigma $, with $1 \leq u, v \leq n$, $1 \leq \sigma \leq w \leq 10^9$. They represent a path from $u$ to $v$ on the map taking on average $w$ time with deviance $\sigma $. It is guaranteed that the graph includes no self loops and each $(u, v)$ pair appears at most ones in the input.

Output

The output should include those points the are possible contact points, in increasing order, on one line. If there are no possible contact points print ‘Thessi leikur verdur sennilega leidinlegur’.

5 6
1 5
1 2 5 2
1 3 1 1
1 4 2 1
3 4 1 1
5 2 2 1
5 4 5 1

2

4 4
1 4
1 2 10 1
1 3 5 1
4 2 5 1
4 3 10 1

Thessi leikur verdur sennilega leidinlegur

13 38
2 10
1 2 2 1
1 11 7 2
1 5 4 1
2 1 2 1
2 3 3 1
3 2 3 1
3 7 2 2
3 4 6 1
4 3 6 1
4 8 7 2
5 1 4 1
5 2 1 1
5 6 4 2
6 5 4 2
6 7 1 1
6 9 8 3
6 12 10 4
7 3 2 2
7 8 8 2
7 9 10 3
8 4 7 2
8 7 8 2
8 10 13 2
9 6 8 3
9 7 10 3
9 10 3 1
9 12 4 2
10 8 16 5
10 9 3 1
10 12 4 2
11 1 7 2
11 12 4 1
11 13 1 1
12 6 10 4
12 9 4 2
12 10 4 2
12 11 4 1
13 11 1 1

6 7 8 11 13