Автобусный тур
Представьте, что вы турист в Варшаве и забронировали автобусную экскурсию, чтобы увидеть удивительную достопримечательность за пределами города. Сначала автобус некоторое время ездит по городу (долгое время, поскольку Варшава — большой город), забирая людей из их отелей. Затем он направляется к удивительной достопримечательности, а через несколько часов возвращается в город, снова заезжая в каждый отель, на этот раз чтобы высадить людей.
По какой-то причине, когда вы это делаете, ваш отель всегда первым посещается для посадки и последним для высадки, что означает, что вам приходится терпеть два не очень удивительных тура по всем местным отелям. Это явно не то, что вы хотите делать (если только по какой-то причине вы не действительно увлечены отелями), так что давайте это исправим. Мы разработаем программное обеспечение, чтобы позволить экскурсионной компании более справедливо маршрутизировать свои автобусные туры — хотя это иногда может означать более длинное общее расстояние для всех, но справедливость есть справедливость, верно?
Для этой задачи есть начальная точка (штаб-квартира экскурсионной компании), h отелей, которые нужно посетить для посадки и высадки, и место назначения (удивительная достопримечательность). Нам нужно найти маршрут, который идет от штаб-квартиры, через все отели, к достопримечательности, затем обратно через все отели (возможно, в другом порядке), и, наконец, обратно в штаб-квартиру. Чтобы гарантировать, что ни один из туристов (и, в частности, вы) не будет вынужден терпеть два полных тура по отелям, мы требуем, чтобы каждый отель, который посещается среди первых h/2 отелей по пути к достопримечательности, также посещался среди первых h/2 отелей на обратном пути. С учетом этих ограничений, мы хотели бы сделать полный автобусный тур как можно короче. Обратите внимание, что эти ограничения могут заставить автобус проехать мимо отеля, не останавливаясь там (это не считается посещением), а затем посетить его позже, как показано в первом примере ввода.
Входные данные
Первая строка каждого теста состоит из двух целых чисел n и m, удовлетворяющих 3 ≤ n ≤ 20 и 2 ≤ m, где n — количество мест (отели, штаб-квартира, достопримечательность), а m — количество пар мест, между которыми автобус может перемещаться.
n различных мест пронумерованы от 0 до n-1, где 0 — это штаб-квартира, 1 до n-2 — это отели, а n-1 — это достопримечательность. Предположим, что между любой парой мест есть не более одного прямого соединения и можно добраться из любого места в любое другое (но не обязательно напрямую).
После первой строки следуют m строк, каждая из которых содержит три целых числа u, v и t, такие что 0 ≤ u, v ≤ n-1, u ≠ v, 1 ≤ t ≤ 3600, указывающие, что автобус может ехать напрямую между местами u и v за t секунд (в любом направлении).
Выходные данные
Для каждого теста выведите номер случая и время в секундах самого короткого возможного тура.