Genius Walk

Time limit2sMemory limit1024 MB

Summary

Find the earliest time Sam can reach city t from s when each road has periodic rain and he cannot stop midway along a road.

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

Problem

Sam found $n$ cities in a new region, connected by $m$ two-way roads. Sam can only move along the roads. He needs to get from city $s$ to city $t$ without being caught in temporal rain. According to the weather forecast, rain falls over the $i$ -th road during the time intervals $[(a_i + b_i) \cdot k + a_i, (a_i + b_i) \cdot (k + 1)]$ for all integers $k$ ( $a_i$ and $b_i$ are positive). To travel along the $i$ -th road, Sam needs $d_i$ units of time, and there must be no rain over that road during the entire trip. Sam can take shelter from the rain in cities, so he can be in a city at any time. Sam can leave a city onto a road at the moment the rain stops, and enter a city from a road at the moment the rain starts.

At time $0$ , Sam is in city $s$ . Find the earliest moment at which he can be in city $t$ .

Input

The first line contains four integers $n$ , $m$ , $s$ , and $t$ : the number of cities, the number of roads, the starting city, and the destination city ( $1 \le n \le 100000$ ; $0 \le m \le 200000$ ; $1 \le s, t \le n$ ). Each of the next $m$ lines describes a road with five integers $u_i$ , $v_i$ , $a_i$ , $b_i$ , and $d_i$ ( $1 \le u_i, v_i \le n$ ; $1 \le a_i, b_i, d_i \le 10^9$ ). Road $i$ connects cities $u_i$ and $v_i$ .

Output

If Sam cannot get from city $s$ to city $t$ , print $-1$ . Otherwise, print the minimum moment at which he can be in city $t$ .

Examples1

Example 1
Input
```
3 2 1 3
1 2 3 4 1
2 3 2 3 2
```
Expected output
```
7
```