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$ ל־Bessie ו־$1 \to 3$ ל־Elsie הן מגיעות יחד.

מחבר הבעיה: Nick Wu, 2015