该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Petr 和 Elsie 想从谷仓前往她们最喜欢的田地，她们同一时间出发，同一时间到达。

农场由 $N$ （ $1 \le N \le 16$ ）块田地组成，标号为 $1 \dots N$ ，田地 $1$ 表示谷仓，田地 $N$ 则是最喜欢的田地。农场建在高山的一侧，因此当 $X \lt Y$ 时，田地 $X$ 的海拔高度比田地 $Y$ 的高。有 $M$ 条小径连接成对的田地。然而，由于每条小径都比较陡峭，因此只能沿着下坡方向通过。例如，某条小径连接了田地 $5$ 和 $8$，那么只能从田地 $5$ 走到田地 $8$，而不能反方向上坡通过。每对田地最多只用一条小径相连，因此 $M \le \frac{N(N-1)}{2}$。

Petr 和 Elsie 通过一条路径的时间可能是不同的。例如，Petr 可能需要花 $10$ 个单位时间，而 Elsie 需要 $20$。Petr 和 Elsie 只会在通过小径时花费时间，穿过田地的时间可以被看作为 $0$。

请你求出 Petr 和 Elsie 为了同时到达她们最喜欢的田地所需要花费的最短时间。

输入格式

输入的第一行包含 $N$ 、 $M$ ，用空格分隔。

加下来 $M$ 行，每行用 $A$ 、 $B$ 、 $C$ 、 $D$ 四个整数描述一条小径。 $A$ 、 $B$ （ $A \lt B$ ）表示小径所连的两个田地编号， $C$、 $D$ （ $1 \le C, D \le 1000$ ）分别表示 Petr 和 Elsie 通过该条小径所需要花费的时间。

输出格式

输出一个整数，表示 Petr 和 Elsie 为了同时到达她们最喜欢的田地所需要花费的最短时间。如果她俩不能同时到达，或者她俩根本无法到达她们最喜欢的田地，输出 IMPOSSIBLE 。

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

2

提示

样例解释

在每条小径上，Petr 总是比 Elsie 快一倍，但是如果 Petr 选择路径 $1 \rightarrow 2 \rightarrow 3$ ，Elsie 选择路径 $1 \rightarrow 3$ ，那么她们可以同时到达最喜欢的田地。