Bessie e sua sorella Elsie vogliono andare dal fienile al campo preferito, partendo esattamente insieme e arrivando esattamente insieme.

La fattoria ha $N$ campi ($1 \leq N \leq 100$) numerati $1 \dots N$: $1$ contiene il fienile, $N$ è il preferito. È su un pendio: $X$ è più alto di $Y$ se $X < Y$. $M$ sentieri collegano coppie, ma sono ripidi e percorribili solo in discesa. Tra $5$ e $8$ si può andare $5 \to 8$, non al contrario in salita. Ogni coppia ha al massimo un sentiero, quindi $M \leq N(N-1)/2$.

I tempi possono differire: per esempio Bessie impiega $10$ unità, Elsie $20$. Consumano tempo solo sui sentieri fra campi: hanno fretta, attraversano i campi in tempo praticamente zero e non aspettano mai in alcun luogo.

Determina il tempo minimo per arrivare al campo preferito esattamente insieme.

Input

La prima riga contiene $N$ e $M$ separati da spazio.

Le successive $M$ righe descrivono sentieri con quattro interi $A$ $B$ $C$ $D$: $A$ e $B$ ($A < B$) sono i campi collegati, $C$ il tempo di Bessie, $D$ quello di Elsie. $C$ e $D$ sono nell’intervallo $1 \ldots 100$.

Output

Stampa un intero, il tempo minimo per arrivare insieme. Se è impossibile o Bessie o Elsie non può affatto raggiungere il campo preferito, stampa IMPOSSIBLE su una riga.

Esempi

Input 1

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

Output 1

2

Nota

Bessie è due volte più veloce su ogni sentiero, ma con $1 \to 2 \to 3$ per Bessie e $1 \to 3$ per Elsie arrivano insieme.

Autore del problema: Nick Wu, 2015