Bessie e sua irmã Elsie querem ir do celeiro ao campo favorito, saindo exatamente juntas e chegando exatamente juntas.

A fazenda tem $N$ campos ($1 \leq N \leq 100$) numerados $1 \dots N$: $1$ contém o celeiro, $N$ é o favorito. Fica numa encosta: $X$ é mais alto que $Y$ se $X < Y$. $M$ caminhos unem pares, mas são tão íngremes que só permitem descer. Entre $5$ e $8$, pode-se ir $5 \to 8$, não ao contrário, subindo. Cada par tem no máximo um caminho, logo $M \leq N(N-1)/2$.

Os tempos podem diferir: por exemplo Bessie leva $10$ unidades e Elsie $20$. Só gastam tempo nos caminhos entre campos: estão com pressa, passam pelos campos em tempo praticamente zero e nunca esperam.

Determine o menor tempo para chegarem ao campo favorito exatamente juntas.

Entrada

A primeira linha contém $N$ e $M$ separados por espaço.

As próximas $M$ linhas descrevem caminhos com quatro inteiros $A$ $B$ $C$ $D$: $A$ e $B$ ($A < B$) são campos conectados, $C$ o tempo de Bessie e $D$ o de Elsie. $C$ e $D$ estão em $1 \ldots 100$.

Saída

Imprima um inteiro, o menor tempo de chegada simultânea. Se for impossível ou Bessie ou Elsie não puder chegar ao campo favorito, imprima IMPOSSIBLE em uma linha.

Exemplos

Entrada 1

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

Saída 1

2

Explicação

Bessie é duas vezes mais rápida em cada caminho, mas seguindo $1 \to 2 \to 3$ enquanto Elsie segue $1 \to 3$, chegam juntas.

Autor do problema: Nick Wu, 2015