Hẹn Gặp

Có $N$ ô đồng được đánh số từ $1$ đến $N$ và $M$ con đường một chiều (chỉ đi từ ô số nhỏ sang ô số lớn). Mỗi con đường từ ô $A$ đến ô $B$ mất $C$ phút cho Bessie và $D$ phút cho Elsie.

Bessie và Elsie xuất phát đồng thời từ ô $1$, cần đến ô $N$ vào cùng một thời điểm. Tìm thời gian nhỏ nhất để cả hai đến ô $N$ cùng lúc, hoặc in IMPOSSIBLE nếu không thể.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$.

• $M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $A$, $B$, $C$, $D$ — con đường từ ô $A$ đến ô $B$ mất $C$ phút cho Bessie, $D$ phút cho Elsie.

Dữ liệu ra

Thời gian nhỏ nhất (số nguyên), hoặc IMPOSSIBLE.

Ràng buộc

• $1\le N\le 16$
• $M\le N(N-1)/2$
• $1\le C,D\le 1000$
• Với mọi con đường $A\to B$: $A<B$

Ví dụ