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).