Odd Cut
Given a connected undirected graph with n vertices and m edges, where each edge has a non-negative integer weight. It is known that n is an odd number. Your task is to partition the vertices into two sets, A and B, such that the following conditions are satisfied:
A and B are disjoint sets that together include all vertices.
Both |A| and |B| must be odd numbers.
The sum of the weights of the edges that have one endpoint in A and the other in B should be minimized.
Input
The first line contains two integers, n and m (1 ≤ n ≤ 200, 1 ≤ m ≤ 2000). The following m lines describe the edges of the graph. Each line contains three integers: the two endpoints of the edge and its weight, which is an integer from 0 to 10^5, inclusive. The vertices are numbered starting from one. It is guaranteed that the graph has no loops, but it may contain multiple edges between the same pair of vertices.
Output
On the first line, output the minimum total weight of the edges that have one endpoint in A and the other in B.
On the second line, output the size of set A.
On the third line, list the vertices that belong to set A.