Description

Little Tim was in an amusement park and finally escaped one day! But he was accidentally spotted by the staff again… So your task is to safely escort Little Tim home. However, the complex traffic in City A gives you a big challenge.

City A has $n$ intersections and $m$ one-way roads. Each road is only open during a certain time interval. For safety, you must choose an escort route that minimizes Tim’s time on the road, that is, minimize the arrival time minus the time when he leaves the amusement park.

Input Format

The first line contains $4$ numbers, $n,m,s,t$. The base is at intersection $s$, and the dock is at intersection $t$.

Each of the next $m$ lines contains $5$ numbers $x,y,b,e,c$, describing a directed road from intersection $x$ to intersection $y$, which is open from time $b$ to time $e$, and takes $c$ time to traverse (you must ensure that the road remains open during the entire traversal; otherwise Tim will be caught). There may be multiple roads between two intersections. The start time is $0$ (of course, you don’t have to depart immediately; you may wait at the base).

If no plan exists that allows Tim to reach the dock, output Impossible.

Output Format

Output one line: the minimal time Tim spends on the road.

4 5 1 4 
1 2 0 1 1 
1 2 0 1 2 
1 3 1 3 2 
2 4 3 4 1 
3 4 3 4 1 

3

Hint

[Sample Explanation #1]

The optimal plan is to stay at node $1$ until time $1$, then go to node $3$, then go to node $4$. The arrival time is $4$. Tim’s time on the road is $4-1=3$.

Constraints

For all testdata:

• $2\leqslant n\leqslant 100$, $0\leqslant m\leqslant 1000$, $1\leqslant s,t\leqslant n$, $s\not= t$.
• $1\leqslant x,y\leqslant n$, $0\leqslant b,e,c\leqslant 10000$, $b< e$.

Translated by ChatGPT 5