3594 -- Escort of Dr. Who How

Language:

Escort of Dr. Who How

Time Limit: 2000MS		Memory Limit: 131072K
Total Submissions: 2903		Accepted: 788

Description

The notorious ringleader and cyber-criminal Derek Wu, better known as Dr. Who How, has been convicted for multiple abductions and cyber-frauds several minutes ago. He will soon be transferred from the court to the prison to serve a life sentence. Intelligence from undercover officers in Dr. Who How’s outlawed gang indicates a possible forcible rescue operation by gang members in the case that Dr. Who How is convicted. To ensure a successful escort, besides adopting enhanced security measures, the police force further desires to minimize the escort time—the time that the motorcade of escort has to spend between departure from the court and arrival at the prison.

The complex traffic condition in the city imposes complications on the police force’s escort effort. While the municipal government has agreed to temporarily shut down a few roads for exclusive police use, the shut-down time windows vary among roads and are generally narrow to avoid excessively disturbing the life of the citizens. The motorcade of escort must pass through any road entirely within its shut-down time window and not use any road that the municipal government has not agreed to shut down.

Given information about all roads available to the police force for the escort, determine the shortest escort time.

Input

The input contains a single test case. The first line contains four integers n, m, s and t (2 ≤ n ≤ 100; 0 ≤ m ≤ 1000; 1 ≤ s, t ≤ n; s ≠ t). There are n junctions, some pairs of which are connected by m roads. The court and the prison are located at the s-th and the t-th junctions, respectively. The next m lines each contain five integers x, y, b, e and c (1 ≤ x, y ≤ n; 0 ≤ b < e ≤ 10⁴; 1 ≤ c ≤ 10⁴), indicating that the directed lanes running from the x-th junction to the y-th junction of a road that takes the motorcade of escort c units of time to pass through will be shut down between time b and e. The earliest time when the motorcade can leave the court is time 0.

Output

If the escort is possible, print the shortest escort time; otherwise, print “Impossible”.

Sample Input

Sample Output

Hint

The sample is depicted in Figure 1. Each junction is represented by a numbered spot. Each road is represented by an arrow labeled with $\langle\langle b,e\rangle,c\rangle$ , its shut-down time window and pass-through time.

Figure 1: Depiction of the sample

The second road listed in the sample is virtually unusable for it takes the motorcade of escort longer time to pass through than it can stay available. The remaining four roads enable the following two escort routes:

$1\stackrel{\!\langle 0,1\rangle}{\to}2\stackrel{\!\langle 3,4\rangle}{\to}4$
$1\stackrel{\!\langle 1,3\rangle}{\to}3\stackrel{\!\langle 3,4\rangle}{\to}4$

(The label $\langle s,t\rangle$ over an arrow indicates that the motorcade passes through the corresponding road between time s and t.) The first route takes four units of escort time, whereas the second takes three, which is the shortest possible.

Source

PKU Campus 2008 (POJ Founder Monthly Contest – 2008.05.10), frkstyc