拯救小 tim

题目描述

小 tim 在游乐场,有一天终于逃了出来!但是不小心又被游乐场的工作人员发现了…所以你的任务是安全地把小 tim 护送回家。但是,A 市复杂的交通状况给你出了一大难题。  A 市一共有 $n$ 个路口,$m$ 条单行马路。但是,每条马路都只有一段时间是开放的。为了安全,你必须选择一条护送路线,使得小 tim 在路上的时间最短,即到家的时刻减去离开游乐场的时刻最短。

输入输出格式

输入格式


第一行 $4$ 个数,分别是 $n,m,s,t$。基地在路口 $s$,码头在路口 $t$。 接下来 $m$ 行每行 $5$ 个数 $x,y,b,e,c$ 表示一条 $x$ 路口到 $y$ 路口的单行线,在 $b$ 时刻到 $e$ 时刻之间开放,需要 $c$ 的时间通过这条路(必须保证行进在路中间时,路一直开放,否则小 tim 会被捉住)。两个路口之间可能会有多条道路。一开始的时刻是 $0$(当然,你可以不用马上出发,在基地多呆一段时间)。 如果不存在任何一种方案使得小 tim 能成功到达码头,输出 `Impossible`。

输出格式


一行,为小 tim 在路上停留的最短时间。

输入输出样例

输入样例 #1

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 

输出样例 #1

3

说明

**【样例解释 #1】** 最优方案应该是,在 $1$ 号点停留至时刻 $1$,然后走到 $3$ 号点,然后走到 $4$ 号点。到达时刻为时刻 $4$。tim 在路上的时间为 $4-1=3$。 ### 数据范围 对于所有测试数据: - $2\leqslant n\leqslant100$,$0\leqslant m\leqslant1000$,$1\leqslant s,t\leqslant n$,$s\not=t$; - $1\leqslant x,y\leqslant n$,$0\leqslant b,e,c\leqslant10000$,$b<e$。