Bessie i jej siostra Elsie chcą dotrzeć z obory na ulubione pole, wyruszając dokładnie jednocześnie i przybywając dokładnie jednocześnie.

Farma ma $N$ pól ($1 \leq N \leq 100$) numerowanych $1 \dots N$: $1$ zawiera oborę, $N$ jest ulubione. Leży na zboczu: $X$ jest wyżej niż $Y$, gdy $X < Y$. $M$ ścieżek łączy pary, lecz są strome i wolno iść tylko w dół. Między $5$ i $8$ można iść $5 \to 8$, nie odwrotnie pod górę. Każda para ma najwyżej jedną ścieżkę, więc $M \leq N(N-1)/2$.

Czasy mogą się różnić: np. Bessie potrzebuje $10$ jednostek, Elsie $20$. Czas zużywają tylko na ścieżkach: spieszą się, przechodzą przez pola praktycznie w zerowym czasie i nigdzie nie czekają.

Wyznacz minimalny czas dotarcia na ulubione pole dokładnie jednocześnie.

Wejście

Pierwszy wiersz zawiera $N$ i $M$ rozdzielone spacją.

Kolejne $M$ wierszy opisuje ścieżki czterema całkowitymi $A$ $B$ $C$ $D$: $A$ i $B$ ($A < B$) to połączone pola, $C$ czas Bessie, $D$ czas Elsie. $C$ i $D$ są w zakresie $1 \ldots 100$.

Wyjście

Wypisz jedną liczbę całkowitą, minimalny czas równoczesnego przybycia. Jeśli jest to niemożliwe lub Bessie albo Elsie w ogóle nie może dojść na ulubione pole, wypisz IMPOSSIBLE w jednym wierszu.

Przykład

Wejście 1

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

Wyjście 1

2

Uwagi

Bessie jest dwa razy szybsza na każdej ścieżce, ale przy $1 \to 2 \to 3$ dla Bessie i $1 \to 3$ dla Elsie przybędą równocześnie.

Autor zadania: Nick Wu, 2015