Maximum forest cover digraph

Input

The input file consists of one or more input sets. Each set begins with a line containing two integers $n$ and $m$ (1 \leq n \leq 200, 0 \leq m \leq 10000). Here, $n$ is the number of vertices in the graph, and $m$ is the number of edges. The next $m$ lines each contain three numbers x_i, y_i, c_i — the start vertex, the end vertex, and the weight of the arc. The digraph does not contain loops, but may contain multiple arcs.

Across all input sets within one test, the total number of arcs does not exceed $10000$.

Output

For each input set, output three lines. The first line should contain the total weight of the optimal forest cover, the second line should contain the number of arcs in the cover, and the third line should contain the numbers of the arcs selected for the cover. Print a blank line after each output block.

Examples