SPOJ Problem Set (classical) 3953. Paid Roads Problem code: MMINPAID

English

Vietnamese

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). 

SAMPLE 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

 
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'. . 

SAMPLE OUTPUT
110

---

Added by:	~!(*(@*!@^&
Date:	2009-02-25
Time limit:	1s
Source limit:	50000B
Languages:	All except: ERL JS PERL 6
Resource:	Northeastern Europe 2002 Western Subregion