Bessie 和她的姐妹 Elsie 想从牛棚前往最喜欢的田地，要求从牛棚恰好同时出发，也恰好同时到达。

农场有 $N$ 块田地（$1 \leq N \leq 100$），编号 $1 \dots N$，田地 $1$ 有牛棚，$N$ 是最喜欢的田地。农场在山坡上，若 $X < Y$，田地 $X$ 的高度就高于 $Y$。$M$ 条路径连接田地对，但每条都很陡，只能下坡走。例如连接 $5$ 与 $8$ 的路径只能沿 $5 \to 8$ 走，反过来会上坡。每对至多一条路径，因此 $M \leq N(N-1)/2$。

走同一条路径时两者用时可能不同，例如 Bessie 用 $10$ 单位时间，Elsie 用 $20$。她们只在田地间路径上耗时：因为赶时间，穿过田地基本不耗时，绝不在任何地方等待。

求两者恰好同时到达最喜欢田地所需的最短时间。

输入格式

第一行包含空格分隔的 $N$ 和 $M$。

接下来 $M$ 行每行以四个整数 $A$ $B$ $C$ $D$ 描述路径：$A$ 和 $B$（$A < B$）是相连田地，$C$ 是 Bessie 用时，$D$ 是 Elsie 用时。$C$ 与 $D$ 都在 $1 \ldots 100$ 内。

输出格式

输出一个整数，表示两者恰好同时到达所需的最小时间。若无法做到，或 Bessie 或 Elsie 完全无法到达最喜欢的田地，单独一行输出 IMPOSSIBLE。

样例

输入格式 1

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

输出格式 1

2

说明

每条路径 Bessie 的速度是 Elsie 的两倍，但 Bessie 走 $1 \to 2 \to 3$、Elsie 走 $1 \to 3$ 就会同时到达。

题目来源：Nick Wu，2015