MMINPAID - Paid Roads

题意翻译

简述: 假如有n个点(编号从1到n)和m条边。 (连接两条边可能有不止一条边)当从a点到b点时,如果之前经过c点,那么只要付P的费用,如果没有经过,就付R的费用。求1到n点最少要花多少费用。 输入: 第一行包含n和m, 然后接着m行每行都有一个a、b、c、P、R的值来描述一条边; 数据范围—— 1 ≤ m, N ≤ 10, 0 ≤ Pi , Ri ≤ 100, Pi ≤ Ri (1 ≤ i ≤ m). 所有值都是整数. 输出:一行为1到n点的最小费用。 如果不存在路径,输出“ impossible ” 。 样例输入 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 样例输出 110

题目描述

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 ai, bi, ci, Pi, Ri (1 `

输出格式


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

输入输出样例

输入样例 #1

\n
4 5\n1 2 1 10 10\n2 3 1 30 50\n3 4 3 80 80\n2 1 2 10 10\n1 3 2 10 50

输出样例 #1

\n
110