Travelling Merchant's Friend


Submit solution

Points: 12 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

You are friends with a travelling merchant, and you are travelling on a directed acyclic graph with N nodes and M edges. The fact that it is acyclic means that it is impossible to start at a node, travel along a valid path of positive length, and return to the starting node.

You were hoping to visit the travelling merchant. You are at node 1, and the travelling merchant is at node N. At each node, you must maintain a nonnegative integer value. Your value determines which edges you can use and how your value changes each time you travel through an edge.

Each edge can be represented as five nonnegative integers: u_i, v_i, t_i, r_i, s_i \;(u_i \neq v_i, \; 1 \leq i \leq M). This means that you may be able to travel from node u_i to node v_i. Let your current value be x. After travelling from node u_i to node v_i, your value will change as such:

\displaystyle 
x =
\begin{cases} 
    x + r_i \quad & x\geq t_i \\
    x - s_i \quad & x < t_i 
\end{cases}

In other words, if your value is at least t_i, your value increases by r_i. Otherwise, it decreases by s_i. Note that the value you maintain must be nonnegative. This means that if travelling along an edge would decrease your value to a negative number, you cannot travel along that edge.

Find the minimum starting value such that you can travel along some valid path from node 1 to node N.

Constraints

For all subtasks,

2 \leq N, M \leq 2 \times 10^5,

1 \leq u_i, v_i \leq N, \; u_i \neq v_i \; (1 \leq i \leq M),

0 \leq t_i, r_i, s_i \leq 3 \times 10^8 \;(1 \leq i \leq M).

Subtask Points Additional Constraints
1 20 t_i = 3 \times 10^8, s_i = 1 \;(1 \leq i \leq M)
2 20 N \leq 3000, t_i \leq 3000 \;(1 \leq i \leq M)
3 20 The graph is a simple path: M = N-1, u_i = i, v_i = i+1 \;(1 \leq i \leq M)
4 40 No additional constraints

Input Specification

The first line of input contains two space-separated integers: N and M.

The next M lines contain 5 space-separated integers: u_i, v_i, t_i, r_i, s_i.

Output Specification

Output the minimum starting value that allows you to travel from node 1 to node N.

If it is impossible to reach node N regardless of the starting value, output Impossible.

Sample Input 1

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

Sample Output 1

2

Explaination for Sample Output 1

Node Value Edge Taken
1 2
2 2 \#3 \;(1, 2, 2, 0, 1)
3 1 \#0 \;(2, 3, 3, 1, 1)
4 1 \#5 \;(3, 4, 1, 0, 3)
5 2 \#2 \;(4, 5, 1, 1, 3)

Sample Input 2

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

Sample Output 2

Impossible

Explaination for Sample Output 2

It is Impossible to travel from node 1 to node 4 on the given graph.


Comments

There are no comments at the moment.