eolymp
bolt
Try our new interface for solving problems
Məsələlər

Немедленная доставка

Немедленная доставка

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Майк и Джон - работники в Немедленной Доставке. Однажды их попросили доставить много пакетов по всему городу.

Транспортная система города, в котором они работают, состоит из перекрестков и дорог, соединяющих эти перекрестки. Все дороги являются двусторонними и все перекрестки связаны друг с другом (напрямую или косвенно).

Майк и Джон должны посетить все перекрестки чтобы доставить все пакеты. Они хотят разбить эту задачу на две части таким образом, чтобы минимизировать время последней доставки.

Giriş verilənləri

Первая строка содержит два целых числа n (1n18) и m - количество перекрестков и дорог.

Следующие m строк описывают дороги. Каждая строка содержит три целых числа: x_i и y_i (1x_i, y_in) - номера перекрестков, соединенных дорогой, и t_i (1t_i1000) - время проезда по ней. Любые два перекрестка соединены не более чем одной дорогой. Никакая дорога не соединяет перекресток сам с собой.

Офис Немедленной Доставки находится на перекрестке с номером 1.

Çıxış verilənləri

В первой строке следует вывести минимальное возможное время, через которое последний пакет может быть доставлен.

Вторая строка должна содержать путь Майка: количество дорог p, пройденных Майком и номера p + 1 перекрестка в порядке их посещения, начиная с перекрестка 1.

В третьей строке следует вывести путь Джона в том же формате.

Nümunə

Giriş verilənləri #1
6 6
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10
Çıxış verilənləri #1
40
4 1 2 3 4 3
3 1 2 5 6