Задача Концертный тур ≡

Условие

Великие ростовские стримеры Четвёрка и Мэлш c недавних пор стали ещё и музыкантами.

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

Однако, будучи новичками в организации туров, Четвёрка и Мэлш не хотят рисковать и тратить много денег на поездки по неизвестным маршрутам. Чтобы сэкономить и выбрать наиболее выгодный путь, они обратились к вам за помощью. Артисты предоставили вам список городов, а также данные о перелётах и поездках на поезде, включая стоимость билетов.

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

Формат входных данных

Входные данные содержат натуральное число N — количество рейсов между городами. А далее идут N строк, в которых указаны числа a_ij b_ij — номера городов, между которыми есть рейс, и s — цена за билет.

Гарантируется, что граф является простым и связным.

Формат выходных данных

Требуется вывести порядок посещаемых городов, начиная и заканчивая с города "0" и минимальную стоимость маршрута, если такой тур возможно организовать. В противном случае выведите "NO".

Ограничения

2 ≤ N ≤ 40
0 ≤ a_ij b_ij ≤ 10
5000 ≤ s ≤ 200000

Примеры тестов

6
0 1 1
0 2 3
0 3 4
1 2 2
1 3 6
2 3 2
            

0 1 2 3 0
9
            

4
0 1 2
0 2 4
0 3 5
1 3 1
            

NO