Trip the Lights Fantastic
Боб Робертс, батько Маленького Боббі з задачі D, працює в Комісії з дорожнього руху в місті середнього розміру. Він відповідає за контроль світлофорів і відправку ремонтних бригад за потреби. У Боба багато вільного часу, і він вирішив з'ясувати, як найшвидше дістатися з однієї точки міста в іншу. У нього є вся необхідна інформація: план вулиць і цикли всіх світлофорів. Щоб спростити задачу, він зробив кілька припущень:
Всі автомобілі рухаються з однаковою максимальною швидкістю. Якщо вони зупиняються на червоне світло, то витрачають 5 секунд на реакцію і набір швидкості. (Тобто, автомобіль стоїть на місці 5 секунд, а потім рухається з максимальною швидкістю. Боб вважає, що за ці 5 секунд світло не встигне знову стати червоним.)
Кожен автомобіль під'їжджає до світлофора на повній швидкості і або проїжджає через нього, якщо світло зелене або жовте, або зупиняється, якщо світло червоне. Автомобілі можуть проїжджати через світлофор, якщо досягають його в момент, коли він щойно переключається на зелене. Автомобілі повинні зупинитися, якщо вони досягають світлофора в момент, коли він переключається на червоне.
Час на виконання поворотів через світлофор ігнорується. Можливе переміщення між будь-якими двома світлофорами, хоча, можливо, не напряму.
Крім того, розвороти заборонені, і маршрути не будуть повертатися на перехрестя. Навіть з урахуванням цих припущень, Бобу важко знайти мінімальні часові шляхи. Давайте подивимося, чи зможете ви йому допомогти.
Вхідні дані
Перша рядок кожного тестового випадку містить чотири додатні цілі числа n, m, s і e, де n (2 ≤ n ≤ 100) — кількість світлофорів (пронумерованих від 0 до n - 1), m — кількість доріг між світлофорами, а s і e (s ≠ e) — початковий і кінцевий світлофори для бажаної поїздки. Далі слідують n рядків виду g y r, що вказують кількість секунд, протягом яких кожен світлофор горить зеленим, потім жовтим, потім червоним. (1 ≤ g, y, r ≤ 100.) Перша з цих рядків стосується світлофора 0, друга — світлофора 1 і так далі. Після цих n рядків слідують m рядків, кожна з яких описує одну дорогу. Ці рядки будуть мати вигляд l1 l2 t, де l1 і l2 — це два світлофори, з'єднані дорогою, а t — це час (в секундах, t ≤ 500) для проїзду по дорозі на повній швидкості — ви повинні додати 5 до цього значення, щоб отримати час поїздки, починаючи з зупинки. Всі дороги двосторонні. У момент часу 0 всі світлофори тільки починають свій зелений період, і ваш автомобіль вважається стоячим на місці біля світлофора s. Оскільки потрібно 5 секунд, щоб почати рух, ви можете припустити, що g + y ніколи не буде менше або дорівнювати 5. Останній тестовий випадок завершується рядком, що містить 0 0 0 0, вказуючи на кінець вводу.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить мінімальний час для поїздки від початкового світлофора до кінцевого. Виведіть результати у форматі mm:ss, вказуючи кількість хвилин і секунд, яке займає поїздка. Якщо кількість секунд менше 10, то додайте перед ним 0 (тобто виведіть 4:05, а не 4:5). Аналогічно, якщо кількість хвилин менше 10, надрукуйте тільки одну цифру (як у 4:05).