题目描述

贝西和她的姐姐埃尔西想从谷仓前往她们最喜欢的田地，她们要在同一时间从谷仓出发，并且在同一时间到达最喜欢的田地。

农场由$N$块田地（1 <= $N$ <= 16）组成，编号为1..$N$，其中田地1是谷仓，田地$N$是最喜欢的田地。农场建在山坡上，如果$X$ < $Y$，则田地$X$的海拔高于田地$Y$。有$M$条小路连接成对的田地。然而，由于每条小路都相当陡峭，只能沿着下坡方向行走。例如，连接田地5和8的小路可以沿着5->8的方向行走，但不能反向行走，因为那会是上坡。每对田地之间最多有一条小路，所以$M$ <= $N(N-1)/2$。

贝西和埃尔西走同一条小路可能需要不同的时间；例如，贝西可能需要10个单位时间，而埃尔西需要20个单位时间。此外，贝西和埃尔西只在田间小路上行走时消耗时间——因为她们很匆忙，穿过田地的时间基本上为零，不会在任何地方停留。

请帮助确定贝西和埃尔西为了在同一时刻到达她们最喜欢的田地而必须花费的最短时间。

输入格式

• 第一行输入包含$N$和$M$，用空格分隔。
• 接下来的$M$行，每行用四个整数$A$、$B$、$C$、$D$描述一条小路，其中$A$和$B$（$A$ < $B$）是小路连接的田地，$C$是贝西走这条小路所需的时间，$D$是埃尔西走这条小路所需的时间。$C$和$D$的范围都是1..1000。

输出格式

• 一个整数，表示贝西和埃尔西到达最喜欢的田地并同时到达所需的最短时间。如果这是不可能的，或者贝西或埃尔西根本无法到达最喜欢的田地，在一行上输出“IMPOSSIBLE”。

样例

样例输入

3 3
1 3 1 2
1 2 1 2
2 3 1 2

样例输出

2

数据范围

1 <= $N$ <= 16，$M$ <= $N(N-1)/2$，$C$和$D$的范围都是1..1000