Grammy has a simple connected undirected graph. Each of the edges has a value written on it. Please choose a simple cycle for her such that the values written on the cycle has maximum range. 

The range of a cycle is the difference between the maximum value and the minimum value written on it. 

A cycle  ( is some edge connecting vertices  and  in the graph) is simple if and only if each edge appears at most once in it. 

To prove that you really found the cycle, you need to output the vertices on the cycle in order. 

It is guaranteed that there is at least one cycle in the graph. 

输入描述:

The first line contains  integers  (), denoting the number of vertices and the number of edges in the graph. It is guaranteed that there is at most one edge between each pair of vertices. 

In each of the next  lines, there are  integers  (), indicating that there is an edge between vertex  and vertex  having value  written on it. 

输出描述:

In the first line, output a single integer, denoting the maximum range of a simple cycle in the graph. 

In the second line, output a single integer , denoting the number of edges in the cycle. It is not hard to find out that the number of edges is equal to the number of vertices in the cycle. 

In the last line, output  integers, denoting the vertices on the cycle in order. Note that these vertices can be repeated since only edges cannot be visited multiple times. 

If there are multiple solutions, output any. 

5 7
1 2 1
1 3 -2
2 3 1
3 4 3
4 5 1
1 5 -1
2 5 2

5
5
1 2 5 4 3

In the first sample, the cycle 1-2-5-4-3-1 has the maximum range of , since the maximum value on the cycle is , and the minimum value on the cycle is , so the maximum range of a cycle is . It can be shown that there are no cycles with a range larger than .