Bessie y su hermana Elsie quieren ir desde su establo a su campo favorito, de tal manera que ellas salgan al mismo tiempo del establo y lleguen también al mismo tiempo a su campo favorito.

La granja es una colección de N campos ~(1 \leq N \leq 100)~ numerados ~1..N~, donde el campo 1 contiene al establo y el campo ~N~ es el campo favorito. La granja está construida en el lado de una colina, con el campo ~X~ en una elevación más alta que el campo ~Y~ si ~X < Y~. Una red de ~M~ caminos conectan pares de campos. Sin embargo, como cada camino es empinado, puede ser seguido únicamente en dirección de bajada. Por ejemplo, un camino conectando el campo 5 con el campo 8 podría ser recorrido únicamente en la dirección ~5 ->~ 8 pero no en el otro sentido, desde que sería de subida. Cada par de campos está conectado por a lo más un camino, entonces ~M \leq N(N-1)/2~.

Podría ser que Bessie y Elsie gasten diferentes cantidades de tiempo para recorrer un camino; por ejemplo Bessie podría demorarse 10 unidades de tiempo y Elsie 20. Aún más, Bessie y Elsie solamente gastan tiempo cunado recorren caminos entre campos – pues ellas están apuradas, ellas siempre pasan a través de un campo en esencialmente en tiempo cero, nunca esperando en ninguna parte.

Por favor ayude a determinar la cantidad mínima que Bessie y Elsie deben tomar con el fin de llegar a su campo favorito en exactamente el mismo momento.

Entrada

La primera línea de entrada contiene ~N~ y ~M~, separados por un espacio.

Cada una de las siguientes ~M~ líneas describen un camino usando cuatro enteros ~A B C D~, donde ~A~ y ~B~ (con ~A < B~) son campos conectados por el camino, ~C~ es el tiempo requerido por Bessie para recorrer el camino y ~D~ es el tiempo requerido para que Elsie recorra el camino. Ambos ~C~ y ~D~ están en el rango ~1..1000~.

Ejemplo de Entrada

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

Salida

Un solo entero, dando el tiempo mínimo requerido para que Bessie y Elise vayan a su campo favorito y lleguen al mismo tiempo. Si es imposible, o si no hay manera de que Bessie y Elsie lleguen al campo favorito, dé como salida la palabra IMPOSSIBLE en una sola línea.

Ejemplo de Salida

2

NOTAS A LA SALIDA: Bessie es el doble de rápida que Elsie en cada camino, peor si Bessie toma el camino ~1->2->3~ y Elsie toma el camino ~1->3~ ellas llegaran al mismo tiempo.