Зміна маршруту
Система доріг у країні з'єднує всі N міст так, що можна подорожувати між будь-якою парою міст, використовуючи наявні дороги. Кожна дорога з'єднує два різні міста, є двосторонньою і має рівно один пункт оплати (плата стягується в обох напрямках). Дороги перетинаються лише в містах, і жодна пара міст не з'єднана більше ніж однією дорогою.
Компанія Dias Transport пропонує одноденну послугу доставки посилок між містами. Кожна посилка повинна бути доставлена з міста A в інше місто B. Для кожної посилки керівництво Dias Transport визначає маршрут обслуговування, що складається з C міст і C-1 доріг: перше місто на маршруті є відправною точкою посилки, а останнє місто є пунктом призначення. Маршрут обслуговування ніколи не проходить двічі через те саме місто, і транспортний засіб, обраний для доставки посилки, може подорожувати лише за визначеним маршрутом.
Одного дня транспортний засіб зламався і був відправлений на ремонт у місто, яке не входило до його маршруту обслуговування. Керівництво Dias Transport хоче дізнатися, яка найнижча загальна вартість, в термінах плати за проїзд, для доставки посилки (тобто, щоб доставити транспортний засіб з міста, де він був відремонтований, до міста призначення), але з додатковою умовою: якщо в якийсь момент транспортний засіб досягає одного з міст, що складають його маршрут обслуговування, він повинен повернутися до слідування за своїм маршрутом обслуговування.
Вхідні дані
Вхід містить декілька тестових випадків.
Перша строка тестового випадку містить чотири цілі числа N, M, C і K (4 ≤ N ≤ 250, 3 ≤ M ≤ N×(N-1)/2, 2 ≤ C ≤ N-1 і C ≤ K ≤ N-1), що представляють, відповідно, кількість міст, кількість доріг, кількість міст у маршруті обслуговування і місто, де транспортний засіб був відремонтований. Міста ідентифікуються цілими числами від 0 до N-1. Маршрут обслуговування є 0, 1, ..., C-1, тобто, відправна точка 0, з 0 йде до 1, з 1 до 2 і так далі, до пункту призначення C-1. Наступні M рядків описують систему доріг. Кожен з цих рядків описує одну дорогу і містить три цілі числа U, V і P (0 ≤ U, V ≤ N-1, U ≠ V, 0 ≤ P ≤ 250), що вказують, що існує дорога, яка з'єднує міста U і V з платою за проїзд вартістю P.
Останній тестовий випадок супроводжується рядком, що містить чотири нулі, розділені пробілами.
Вихідні дані
Для кожного тестового випадку ваша програма повинна вивести один рядок, що містить одне ціле число, мінімальну загальну вартість плати за проїзд для доставки транспортного засобу до міста призначення.