Задача №112731. Сусанин
Польская армия движется из Костромы в деревню Домнино. Два гетмана Стефан и Константин руководят армией. Стефан изучил карту дорог Костромской губернии и каждую ночь он ведет армию от одной деревни к некоторой другой по некоторой дороге. Константин достал карту секретных троп между деревнями и каждый день он возглавляет марш-бросок армии вдоль одной из этих троп. Каждый гетман перед маршем спрашивает дорогу у Ивана Сусанина.
Длина каждой дороги указана на карте Стефана. Поэтому Стефан знает минимальное расстояние от каждой деревни до Домнино, аналогично Константин знает минимальное расстояние до Домнино по своей карте. Иван Сусанин каждый раз выбирает дорогу для Стефана или тропу для Константина так, что минимальное расстояние между войском и Домнино по соответствующей карте все время строго убывает.
Помогите Ивану найти самый длинный путь в Домнино, удовлетворяющий этим условиям.
Первая строка входа содержит три целых числа N , S и T — количество деревень, номер начальной деревни и номер деревни Домнино (2 ≤ N ≤ 1000, 1 ≤ s , t ≤ N ) . Начальная точка не совпадает с Домнино.
Далее идут описание карты Стефана и карты Константина
Первая строка описания карты содержит число M — количество дорог или троп соответственно (1 ≤ M ≤ 10 5 ) . Каждая из следующих М строк содержит 3 целых числа a , b и l — описывающих дорогу/тропу между пунктами a и b с указанием длины l (1 ≤ a , b ≤ N ;1 ≤ l ≤ 10 6 ) .
Выведите общую длину пути (вдоль дорог и троп), который Сусанин заставит пройти польскую армию. Если он может заставить армию ходить вечно, так и не достигая Домнино, то выведите - 1 .
| № | Номера тестов | Описание | Баллы |
| 1. | 1-2 | Тесты из условия | 0 |
| 2. | 3 - 14 |
N <= 10 |
40 |
| 3. | 15-25 | Полные ограничения | 60 |
Баллы за группу ставятся только при прохождении всех тестов этой группы
5 1 5 5 1 2 2 1 4 2 2 3 1 3 4 1 5 3 1 4 1 2 2 2 4 2 2 3 1 2 5 2
-1
3 1 3 4 1 2 10 2 3 10 1 3 20 2 3 30 4 2 1 10 1 3 10 1 1 10 2 3 10
20