Одинарная скидка
Алекс живёт в городе
1 и хочет добраться до города n. Он стремится найти маршрут с минимальной общей стоимостью перелётов, учитывая, что у него есть купон на скидку. Этот купон можно использовать только один раз, чтобы заплатить половину цены за один из перелётов в пути. Если цена перелёта равна x, то при применении купона она становится .
Определите минимальную стоимость маршрута из города 1 в город n.Входные данные
В первой строке даны два целых числа
n и m (), где n — количество городов, а m — количество перелётов.Далее следует
m строк, каждая из которых описывает перелёт. В каждой строке указаны три целых числа a, b и (). Это означает, что есть двунаправленный перелёт между городами a и b стоимостью .Выходные данные
Выведите одно число — стоимость самого дешёвого маршрута из города
1 в город n.Примеры
Вход | Выход |
6 6
1 2 7
2 3 5
3 6 4
1 4 8
4 5 10
5 6 9 | 12 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB