Непарний розріз

Задано зв'язний неорієнтовний граф з n вершин та m рёбер. Ребрам приписано невід'ємні цілі васги. Відомо, що n парне. Знайдіть розбиття множини вершин на множини A та B таке, щоб виконувались наступні умови:

1. A

   

   B =

   

   ,

2. |A| та |B| - непарні числа,

3. суммарна вага ребер, один кінець яких знаходиться в A, у другий - у B, мінімальна.

Вхідні дані

У першому рядку знаходиться два числа - n та m (1 ≤ n ≤ 200, 1 ≤ m ≤ 2000). У наступних m рядках знаходяться описи ребер графа. Кожен з них містить номери кінців ребра та його вагу - ціле число від 0 до 10^5, включно. Вершини графа нумеруються з одиниці. Гарантується, що у графі немає петель, хоча можуть бути кратні ребра.

Вихідні дані

Виведіть у першому рядку шукану мінімальну вагу ребер.

У другому рядку виведіть розмір множини A.

У третьому рядку виведіть номери вершин, які входять у цю множину.

Приклади