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