For a positive-weighted undirected graph $G$ with vertices numbered $0$ to $v-1$ and edges numbered $0$ to $e-1$, each edge has a given positive weight $C_i$.

In an undirected graph, a sequence of edges is called a circuit of $G$ if the endpoint of each edge is the starting point of the next edge, and the starting point of the first edge is the same as the endpoint of the last edge.

JYY wants to find a circuit with the maximum sum of edge weights. However, you realize that by repeatedly traversing the same edge back and forth, the answer can become infinitely large. Therefore, JYY has modified the problem to finding a circuit that maximizes the XOR sum of the edge weights. Specifically, starting from node $0$, you must return to node $0$ following a sequence of edges such that the XOR sum of all edge weights in the sequence is maximized.

Fortunately, the number of edges in graph $G$ is not much larger than the number of vertices.

JYY does not require you to provide a simple path, but he believes that traversing any edge 3 or more times is inappropriate. Therefore, you need to provide a path with the maximum XOR sum where each edge is traversed at most twice.

Input

The first line contains two space-separated integers $N$ and $M$, representing the number of vertices and edges in the graph, respectively.

The next $M$ lines each contain three integers $A_i, B_i, C_i$, representing an undirected edge $(A_i, B_i)$ in $G$ with weight $C_i$.

$G$ may contain self-loops and multiple edges.

Output

The output contains two lines.

The first line contains an integer representing the maximum XOR sum.

The second line contains a sequence of integers representing the indices of the edges in the path.

You may output any valid sequence.

Examples

Input 1

3 5
0 0 5
0 1 7
1 0 8
1 2 5
0 2 8

Output 1

15
0 0 1 2 4 4

Note

For the first example, note that the XOR sum of edge $1$ and edge $2$ is $15$, and it is impossible to obtain a larger answer. Thus, $\{1, 2\}$ is a valid sequence of edge indices. Of course, one can traverse edges repeatedly in any irrelevant way (as long as each edge is traversed at most twice).

Constraints

• For 20% of the data: $N \le 10, M = N+1, C_i \le 16$
• For 40% of the data: $N \le 100, M = N+2, C_i \le 128$
• For 60% of the data: $N \le 1000, C_i \le 1024$
• An additional 10% of the data satisfies $M = N$
• For 100% of the data: $N, M \le 10^5$ and $M \le N+10$, $C_i < 2^{30}$
• For 100% of the data, the graph $G$ is guaranteed to be connected.