Задачи
Нечётный разрез
Нечётный разрез
Задан связный неориентированный граф из \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}.
В третьей строке выведите номера вершин, которые входят в это множество.
Входные данные #1
6 9 6 1 1 6 2 7 2 1 1 1 4 2 2 4 4 1 3 3 3 4 1 3 5 6 4 5 2
Выходные данные #1
7 3 1 3 5