Bessie und ihre Schwester Elsie wollen von der Scheune zum Lieblingsfeld, wobei sie genau gleichzeitig aufbrechen und genau gleichzeitig ankommen.

Die Farm hat $N$ Felder ($1 \leq N \leq 100$) mit Nummern $1 \dots N$: $1$ enthält die Scheune, $N$ ist das Lieblingsfeld. Sie liegt am Hang: $X$ ist höher als $Y$, wenn $X < Y$. $M$ Wege verbinden Paare, sind aber steil und nur bergab begehbar. Zwischen $5$ und $8$ geht $5 \to 8$, nicht umgekehrt bergauf. Jedes Paar hat höchstens einen Weg, also $M \leq N(N-1)/2$.

Ihre Zeiten können verschieden sein: etwa $10$ Einheiten für Bessie und $20$ für Elsie. Zeit brauchen sie nur auf Wegen zwischen Feldern: Sie haben es eilig, durchqueren Felder praktisch in Nullzeit und warten nirgendwo.

Bestimme die kürzeste Zeit, um genau gleichzeitig das Lieblingsfeld zu erreichen.

Eingabe

Die erste Zeile enthält $N$ und $M$ durch ein Leerzeichen getrennt.

Die nächsten $M$ Zeilen beschreiben Wege mit vier ganzen Zahlen $A$ $B$ $C$ $D$: $A$ und $B$ ($A < B$) sind die verbundenen Felder, $C$ Bessies Zeit, $D$ Elsies Zeit. $C$ und $D$ liegen in $1 \ldots 100$.

Ausgabe

Gib eine ganze Zahl für die minimale Zeit zur gleichzeitigen Ankunft aus. Ist das unmöglich oder kann Bessie oder Elsie das Lieblingsfeld überhaupt nicht erreichen, gib IMPOSSIBLE in einer Zeile aus.

Beispiele

Eingabe 1

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

Ausgabe 1

2

Hinweis

Bessie ist auf jedem Weg doppelt so schnell, aber mit $1 \to 2 \to 3$ für Bessie und $1 \to 3$ für Elsie kommen sie gleichzeitig an.

Aufgabenautor: Nick Wu, 2015