Problem B
Busy Roads

Robert lives in ERPLand, a country with $N$ cities numbered 1 to $N$. Each day in this country has $C$ seconds, numbered 0 to $C - 1$. There are $M$ bi-directional roads connecting pairs of cities. Road $i$ connects cities $A_ i, B_ i$, takes Robert $T_ i$ seconds to travel through, and can only be entered between the $L_ i$-th and $R_ i$-th second (both inclusive) in each day (no restriction on exit time). It is possible to get from any city to any other city directly or indirectly using the roads, and there might be multiple roads connecting the same pair of cities.

Robert lives in city 1, and wants to get to city $N$ to visit his friend, Bert. He is allowed to wait in cities to take a break, sightsee, or just wait for roads to open. Help him find out the minimum amount of time in seconds he needs to get to city $N$ if he starts at time 0 seconds on some day.

Input

The first line of input contains three two positive integers $N$, $M$, and $C$ denoting the number of cities, number of roads and the number of seconds in each day respectively $(2 \leq N \leq 100000, N - 1 \leq M \leq 200000, 1 \leq C \leq 10^9)$.

Each of the following $M$ lines contains 5 integers $A_ i, B_ i, T_ i, L_ i, R_ i$ which are as described above $(1 \leq A_ i, B_ i \leq N, A_ i \neq B_ i, 1 \leq T_ i \leq 10^9, 0 \leq L_ i \leq R_ i < C)$.

It is guaranteed that Robert can get from city 1 to city N.

Output

Output a single integer, the minimum amount of time in seconds he needs to get from city 1 to city $N$.

3 3 10
1 2 3 0 5
1 3 1 7 8
3 2 4 3 3

7

5 5 10
1 2 1 6 8
1 3 4 3 5
2 4 4 1 5
3 4 2 2 6
4 5 6 3 7

20