Bessie et sa sœur Elsie veulent aller de la grange à leur champ préféré, en partant exactement ensemble et en arrivant exactement ensemble.

La ferme a $N$ champs ($1 \leq N \leq 100$) numérotés $1 \dots N$ : $1$ contient la grange, $N$ est le préféré. Elle est sur une pente : le champ $X$ est plus haut que $Y$ si $X < Y$. $M$ chemins relient des paires, mais sont si raides qu’ils se parcourent seulement en descente. Entre $5$ et $8$, on peut aller $5 \to 8$, pas dans l’autre sens, en montée. Chaque paire a au plus un chemin, donc $M \leq N(N-1)/2$.

Les durées peuvent différer : Bessie prend par exemple $10$ unités, Elsie $20$. Elles ne passent du temps que sur les chemins entre champs : pressées, elles traversent les champs en un temps pratiquement nul et n’attendent jamais.

Déterminez la durée minimale pour arriver au champ préféré exactement ensemble.

Entrée

La première ligne contient $N$ et $M$ séparés par un espace.

Les $M$ lignes suivantes décrivent des chemins par quatre entiers $A$ $B$ $C$ $D$ : $A$ et $B$ ($A < B$) sont les champs reliés, $C$ la durée de Bessie, $D$ celle d’Elsie. $C$ et $D$ sont dans $1 \ldots 100$.

Sortie

Affichez un entier, la durée minimale d’arrivée simultanée. Si cela est impossible ou si Bessie ou Elsie ne peut pas du tout atteindre le champ préféré, affichez IMPOSSIBLE sur une ligne.

Exemples

Entrée 1

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

Sortie 1

2

Remarque

Bessie est deux fois plus rapide sur chaque chemin, mais avec $1 \to 2 \to 3$ pour Bessie et $1 \to 3$ pour Elsie, elles arrivent ensemble.

Auteur du problème : Nick Wu, 2015