Cut

Determine the minimum cut between vertices 1 and n in the provided undirected graph.

Input

The first line of the input contains two integers: n (1 ≤ n ≤ 100), representing the number of vertices, and m, representing the number of edges. The following m lines describe the edges. Each edge is defined by the vertices it connects and its capacity, which is a positive integer not exceeding ten million. Note that no two vertices are connected by more than one edge.

Output

The first line of the output should display the number of edges in the minimum cut and their total capacity. The second line should list the edge numbers in increasing order, corresponding to the order they were provided in the input.

Examples