题目描述

有$m$条道路连接着$N$个城市（编号为$1$到$N$）。两个城市之间可能有多条道路相连。其中部分道路是收费的。对于从城市$a_i$到城市$b_i$的收费道路$i$，有两种付费方式：

1. 提前付费：在城市$c_i$（可能与$a_i$相同或不同）支付费用$P_i$；
2. 事后付费：在到达城市$b_i$后支付费用$R_i$。

要求编写程序，找出从城市$1$到城市$N$的最小费用路径。

输入格式

第一行包含两个整数$N$和$m$，分别表示城市数量和道路数量。
接下来$m$行，每行描述一条道路，包含五个整数$a_i, b_i, c_i, P_i, R_i$，相邻数值用空格分隔。
所有数值均为整数，满足$1 \leq m, N \leq 10$，$0 \leq P_i, R_i \leq 100$，且$P_i \leq R_i$。

输出格式

输出从城市$1$到城市$N$的最小费用。若无法到达，输出单词‘impossible’。

输入数据示例 1

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  

输出数据示例 1

110  

题目来源

Northeastern Europe 2002, Western Subregion