Задано зв'язний неорієнтовний граф з \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}. У третьому рядку виведіть номери вершин, які входять у цю множину.