تريد 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 أسرع بمرتين على كل مسار، لكن إذا سلكت $1 \to 2 \to 3$ وسلكت Elsie $1 \to 3$ تصلان معًا.

مؤلف المسألة: Nick Wu، 2015