D. Обход графа
ограничение по времени на тест
0.5 second
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

Вам задан взвешенный неориентированный граф. Ваша задача найти наименьшую длину такого цикла, который начинается (и заканчивается) в вершине 1 и проходит по каждому ребру хотя бы раз. Граф может содержать кратные ребра (т.е. несколько ребер между парой вершин) и петли (ребра из вершины в себя).

Входные данные

Первая строке содержит пару чисел n, m (1 ≤ n ≤ 15, 0 ≤ m ≤ 2000), n — количество вершин в графе, а m — количество ребер. Далее в m строках заданы ребра графа тройками чисел x, y, w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10000), x, y — концы ребра, а w — длина ребра.

Выходные данные

Выведите искомую длину цикла или -1 если такой не существует.

Примеры
Входные данные
3 3
1 2 1
2 3 1
3 1 1
Выходные данные
3
Входные данные
3 2
1 2 3
2 3 4
Выходные данные
14