Автобусний тур#3389
Уявіть, що ви турист у Варшаві і забронювали автобусний тур, щоб відвідати захоплюючу пам'ятку за містом. Спочатку автобус їздить містом деякий час (довго, адже Варшава - велике місто), підбираючи пасажирів у їхніх готелях. Потім він прямує до пам'ятки, а через кілька годин повертається в місто, знову заїжджаючи до кожного готелю, цього разу, щоб висадити пасажирів.
З якоїсь причини ваш готель завжди перший для підбору і останній для висадки, що означає, що вам доводиться терпіти два не дуже захоплюючі екскурсійні тури по всіх місцевих готелях. Це явно не те, що ви хочете робити (якщо тільки з якоїсь причини ви дійсно не захоплюєтеся готелями), тому давайте це виправимо. Ми розробимо програмне забезпечення, яке дозволить екскурсійній компанії справедливіше маршрутизувати свої автобусні тури — хоча це іноді може означати довшу загальну відстань для всіх, але справедливість є справедливістю, чи не так?
У цій задачі є початкова локація (штаб-квартира екскурсійної компанії), готелів, які потрібно відвідати для підбору та висадки, і місце призначення (дивовижна пам'ятка). Нам потрібно знайти маршрут, який починається від штаб-квартири, проходить через усі готелі до пам'ятки, потім повертається через усі готелі знову (можливо, в іншому порядку), і нарешті повертається до штаб-квартири. Щоб гарантувати, що жоден з туристів (і, зокрема, ви) не змушений терпіти два повних тури по готелях, ми вимагаємо, щоб кожен готель, який відвідується серед перших готелів на шляху до пам'ятки, також відвідувався серед перших готелів на зворотному шляху. З урахуванням цих обмежень, ми хотіли б зробити повний автобусний тур якомога коротшим. Зверніть увагу, що ці обмеження можуть змусити автобус проїхати повз готель, не зупиняючись там (це не вважається відвідуванням), а потім відвідати його пізніше, як показано в першому прикладі вхідних даних.
Перша строка кожного тестового випадку складається з двох цілих чисел та , що задовольняють 3 \le n \le 20 та 2 \le m, де - це кількість локацій (готелі, штаб-квартира, пам'ятка), а - це кількість пар локацій, між якими автобус може подорожувати.
різних локацій пронумеровані від до n-1, де - це штаб-квартира, до n-2 - це готелі, а n-1 - це пам'ятка. Припустимо, що існує не більше одного прямого з'єднання між будь-якою парою локацій і можливо подорожувати від будь-якої локації до будь-якої іншої (але не обов'язково безпосередньо).
Після першої строки йдуть рядків, кожен з яких містить три цілі числа , та такі, що 0 \le u, v \le n-1, u \ne v, 1 \le t \le 3600, що вказує, що автобус може їхати безпосередньо між локаціями та за секунд (в обох напрямках).
Для кожного тестового випадку виведіть номер випадку та час у секундах найкоротшого можливого туру.
Приклад 1