Занятие 15

Фермер Джон хочет как можно дешевле организовать свою систему распределения воды, но он не хочет, чтобы его конкурент фермер Плуто мог предсказать маршруты, которые он выбирает. Фермер Джон знает, что такая задача обычно требует самого дешевого способа прокладки труб, поэтому он решил использовать второй по стоимости способ.

Дан список всех двунаправленных труб, которые могут соединять множество из `W` (`3\ ≤\ W\ ≤\ 2\ 000`) станций с водой (каждая из которых может быть встроена в колодец). Ваша задача – найти второй из самых дешевых способов соединить насосные станции, используя не более чем `P` (`P\ ≤\ 20\ 000`) труб с заданной стоимостью каждой трубы. Не должно быть трубы, соединяющей станцию саму с собой. Не должно быть двух труб, соединяющих дважды одну и ту же пару станций.

Гарантируется, что есть только один самый дешевый способ распределить воду, и что существует, как минимум, два способа распределить воду. Все стоимости – положительные числа, помещающиеся в 16-битное целое. Водная станция идентифицируется своим номером – целым числом в диапазоне `1..W`.

Первая строка ввода – два разделенных пробелом целых числа, `W` и `P`, Каждая из следующих `P` строк описывают одну трубу и содержит 3 числа, разделенных пробелом, – номера станций начала и конца трубы, а также стоимость этой трубы.

Вывести одно целое число – вторую минимальная стоимость конструирования системы распределения воды.

5 7
1 2 3
2 3 4
1 4 7
2 4 11
2 5 9
5 4 5
3 5 8

20