# Problem D

Esports on my Mind

Languages
en
is
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.

## 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’.

Sample Input 1 | Sample Output 1 |
---|---|

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 |

Sample Input 2 | Sample Output 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 |

Sample Input 3 | Sample Output 3 |
---|---|

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 |