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