Задан связный неориентированный граф из \textbf{n} вершин и \textbf{m} рёбер. Рёбрам приписаны неотрицательные целые веса. Известно, что \textbf{n} чётное. Найдите разбиение множества вершин на множества \textbf{A} и \textbf{B} такое, чтобы выполнялись следующие условия: \begin{enumerate} \item \textbf{A} \includegraphics{https://static.e-olymp.com/content/c3/c3f9ed8e48c92a5a2a841d0ad412343541a6a236.jpg} \textbf{B} = \includegraphics{https://static.e-olymp.com/content/4a/4a84637a3e45784a6f542dae8121ca18138bc8e6.jpg} , \item \textbf{|A|} и \textbf{|B|} - нечётные числа, \item суммарный вес рёбер, один конец которых находится в \textbf{A}, а другой - в \textbf{B}, минимален. \end{enumerate} \InputFile В первой строке находится два числа - \textbf{n} и \textbf{m} (\textbf{1} ≤ \textbf{n} ≤ \textbf{200}, \textbf{1} ≤ \textbf{m} ≤ \textbf{2000}). В следующих \textbf{m} строках находятся описания рёбер графа. Каждая из них содержит номера концов ребра и его вес - целое число от \textbf{0} до \textbf{10^5}, включительно. Вершины графа нумеруются с единицы. Гарантируется, что в графе нет петель, хотя могут быть кратные рёбра. \OutputFile Выведите в первой строке искомый минимальный вес рёбер. Во второй строке выведите размер множества \textbf{A}. В третьей строке выведите номера вершин, которые входят в это множество.