Bessie và người chị em gái Elsie muốn đi từ chuồng đến cánh đồng yêu thích, rời chuồng đúng cùng lúc và đến đúng cùng lúc.

Trang trại gồm $N$ cánh đồng ($1 \leq N \leq 100$) đánh số $1 \dots N$: $1$ có chuồng, $N$ là yêu thích. Trang trại trên sườn đồi: $X$ cao hơn $Y$ nếu $X < Y$. $M$ đường nối các cặp nhưng dốc nên chỉ đi xuống được. Ví dụ giữa $5$ và $8$ có thể đi $5 \to 8$, không ngược lại vì lên dốc. Mỗi cặp có tối đa một đường, nên $M \leq N(N-1)/2$.

Thời gian đi đường có thể khác: ví dụ Bessie mất $10$ đơn vị, Elsie $20$. Chỉ đi trên đường giữa các đồng mới mất thời gian: họ vội nên qua đồng trong thời gian gần như không và không đợi ở đâu.

Tìm thời gian ngắn nhất để đến cánh đồng yêu thích đúng cùng lúc.

Dữ liệu vào

Dòng đầu chứa $N$ và $M$ cách nhau bởi dấu cách.

$M$ dòng tiếp mô tả đường bằng bốn số nguyên $A$ $B$ $C$ $D$: $A$ và $B$ ($A < B$) là hai đồng nối nhau, $C$ thời gian Bessie, $D$ thời gian Elsie. $C$ và $D$ đều trong $1 \ldots 100$.

Dữ liệu ra

In một số nguyên, thời gian nhỏ nhất đến đồng yêu thích cùng lúc. Nếu không thể, hoặc Bessie hay Elsie không thể đến đó chút nào, in IMPOSSIBLE trên một dòng.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2

Ghi chú

Bessie nhanh gấp đôi trên mỗi đường, nhưng với $1 \to 2 \to 3$ cho Bessie và $1 \to 3$ cho Elsie, họ đến cùng lúc.

Tác giả bài toán: Nick Wu, 2015