Непарний розріз#5467
Дано зв'язний неорієнтований граф з вершинами і ребрами. Кожному ребру приписано невід'ємну цілу вагу. Відомо, що — непарне число. Необхідно розбити вершини на дві множини, і , так, щоб виконувалися наступні умови:
і — неперетинні множини, об'єднання яких охоплює всі вершини.
Потужності обох множин і — непарні числа.
Сумарна вага ребер, один кінець яких належить , а інший , мінімальна.
У першому рядку містяться два цілі числа: і (1 \leq n \leq 200, 1 \leq m \leq 2000). У наступних рядках наведено описи ребер графа. Кожна з них містить три цілі числа — номери кінців ребра та його вагу (ціле число від до 10^5 включно). Вершини графа нумеруються з одиниці. Гарантовано, що в графі немає петель, але можуть бути кратні ребра.
У першому рядку виведіть мінімальну спільну вагу ребер, що мають кінці у різних множинах. У другому рядку виведіть розмір множини . У третьому рядку виведіть номери вершин, що входять до цієї множини.
Приклад 1