Odd Cut#5467
Given a connected undirected graph with vertices and edges. Each edge has a non-negative integer weight. It is known that is an odd number. Your task is to partition the vertices into two sets, and , such that the following conditions are satisfied:
and are disjoint sets that together include all vertices.
Both and are odd numbers.
The sum of the weights of the edges that have one endpoint in and the other in is minimized.
The first line contains two integers, and (1 \leq n \leq 200, 1 \leq m \leq 2000). The following 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 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.
On the first line, output the minimum total weight of the edges that have one endpoint in and the other in . On the second line, output the size of set . On the third line, list the vertices that belong to set .
Example 1