Bessie y su hermana Elsie quieren ir del establo a su campo favorito, saliendo y llegando exactamente a la vez.
La granja tiene $N$ campos ($1 \leq N \leq 100$), numerados $1 \dots N$: $1$ tiene el establo, $N$ es el favorito. Está en una ladera: $X$ está más alto que $Y$ si $X < Y$. $M$ caminos unen parejas, pero son tan empinados que solo pueden recorrerse cuesta abajo. Entre $5$ y $8$ se puede ir $5 \to 8$, no al revés, cuesta arriba. Cada pareja tiene como máximo un camino, así que $M \leq N(N-1)/2$.
Pueden tardar distinto en un camino: por ejemplo Bessie $10$ unidades, Elsie $20$. Solo consumen tiempo en caminos entre campos: tienen prisa, cruzan campos en tiempo prácticamente cero y nunca esperan.
Determina el tiempo mínimo para llegar al campo favorito exactamente a la vez.
Entrada
La primera línea contiene $N$ y $M$ separados por espacio.
Las siguientes $M$ líneas describen caminos con cuatro enteros $A$ $B$ $C$ $D$: $A$ y $B$ ($A < B$) son los campos unidos, $C$ el tiempo de Bessie y $D$ el de Elsie. $C$ y $D$ están en $1 \ldots 100$.
Salida
Imprime un entero, el tiempo mínimo de llegada simultánea. Si es imposible o Bessie o Elsie no puede llegar al campo favorito, imprime IMPOSSIBLE en una línea.
Ejemplos
Entrada 1
3 3 1 3 1 2 1 2 1 2 2 3 1 2
Salida 1
2
Nota
Bessie es el doble de rápida en cada camino, pero si recorre $1 \to 2 \to 3$ y Elsie $1 \to 3$, llegan a la vez.
Autor del problema: Nick Wu, 2015