Cut

Input

The first line contains two integers $n$ (1 \leq n \leq 100) — the number of vertices, and $m$ — the number of edges. The following $m$ lines each describe an edge, given by the numbers of the vertices it connects and its capacity (a positive integer not exceeding ten million). No two vertices are connected by more than one edge.

Output

The first line should output the number of edges in the minimum cut and their total capacity. The next line should contain the list of edge numbers in increasing order (edges are numbered in the order given in the input).

Examples