Беси и её сестра Эльза хотят путешествовать от амбара
к любимому полю, так чтобы уходит в одно и то же время от
амбара и приходить в одно и то же время к любимому полю.
Ферма представляет собой N полей (1 <= N <= 100), пронумерованных
от 1 до N, где поле 1 – амбар, а поле N – любимое поле.
Ферма построена на склоне холма и поле X будет выше, чем поле Y,
если X каждая дорожка довольно крутая, можно двигаться только вниз.
Например, по дорожке, соединяющей поля 5 и 8 можно двигаться
только от поля 5 к полю 8 и нельзя в противоположном направлении.
Каждая пара полей соединена не более чем одной дорожкой, поэтому
M <= N(N-1)/2.
Беси и Эльза тратят разное количество времени на прохождение
дорожек. Например, Беси нужно 10 единиц времени, чтобы пройти
некоторую дорожку, а Эльзе – 20. Кроме того, они всегда проходят
поля за нулевое время.
Пожалуйста, помогите определить минимальное время, которое
потребуется Беси и Эльзе чтобы достичь любимого поля в один
и тот же момент времени.
Формат входных данных
Первая строка ввода содержит N и M, разделённые одиночным
пробелом.
Каждая из последующих M строк описывает некоторую дорожку
четырьмя целыми числами A B C D, где A и B (A соединённые дорожкой, C – время, требуемое Беси на прохождение
этой дорожки. D – время, требуемое Эльзе на прохождение этой
дорожки. C и D оба в диапазоне 1..1000.
Вывод (файл meeting.out)
Одно целое число, минимальное время, требуемое Беси и Эльзе
чтобы придти на любимое поле в одно и то же время. Если невозможно,
чтобы Беси и Эльза пришли в одно и то же время, выведите IMPOSSIBLE.
Примечание
Беси в два раза быстрее Эльзы на каждой дорожке,
поэтому если Беси пойдёт по пути 1->2->3, а Эльза – по пути 1->3,
они придут в одно и то же время.