MMINPAID - Paid Roads

A network of m roads connects N cities (numbered from 1 to N). There may be more than one road connecting one city with another. Some of the roads are paid. There are two ways to pay for travel on a paid road i from city ai to city bi:

  • in advance, in a city ci (which may or may not be the same as ai);
  • after the travel, in the city bi. The payment is Pi in the first case and Ri in the second case. Write a program to find a minimal-cost route from the city 1 to the city N.

Input

The first line of the input contains the values of N and m. Each of the following m lines describes one road by specifying the values of ai, bi, ci, Pi, Ri (1 ≤ i ≤ m). Adjacent values on the same line are separated by one or more spaces. All values are integers, 1 ≤ m, N ≤ 10, 0 ≤ Pi, Ri ≤ 100, Pi ≤ Ri (1 ≤ i ≤ m).

Output

The first and only line of the output must contain the minimal possible cost of a trip from the city 1 to the city N. If the trip is not possible for any reason, the line must contain the word 'impossible'.

Example

Input:
4 5
1 2 1 10 10
2 3 1 30 50
3 4 3 80 80
2 1 2 10 10
1 3 2 10 50 Output: 110

Added by:psetter
Date:2009-02-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Northeastern Europe 2002 Western Subregion

hide comments
2020-01-17 06:20:25
just bfs with state = (vertex, mask), dp is not needed
2019-02-03 04:58:15
why always wrong in test case 8,can anyone help me

Last edit: 2019-02-03 05:01:03
2018-05-16 23:23:53
very conceptual problem. try visualizing the states for a node.

Last edit: 2018-05-16 23:28:05
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.