SP3953 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 $a_i$ to city $ b_{i} $: - in advance, in a city $c_{i} $ (which may or may not be the same as $a_{i}$); - after the travel, in the city $b_{i}$. The payment is $P_{i}$ in the first case and $R_{i} $ in the second case. Write a program to find a minimal-cost route from the city $1$ to the city $N$.

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 $a_i,b_i,c_i,P_i,R_i(1 \le i \le m)$. Adjacent values on the same line are separated by one or more spaces. All values are integers, $1 \le m, N \le 10$ $0 \le P_i \le R_i \le 100$ $(1 \le i \le m)$.

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