8577: Maximum Range

链接：https://ac.nowcoder.com/acm/contest/33192/L
来源：牛客网
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 i1−e1−i2−e2−⋯−ik−ek−i1i_1 - e_1 - i_2 - e_2 - \cdots - i_k - e_k - i_1i1−e1−i2−e2−⋯−ik−ek−i1 (eje_jej is some edge connecting vertices iji_jij and ijmodk+1i_{j\bmod k+1}ijmodk+1 in the graph) is simple if and only if each edge appears at most once in it. 

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

The first line contains $2$ integers $n,m$ (3≤n≤m≤1053 \leq n \leq m \leq 10^53≤n≤m≤105), 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 $m$ lines, there are $3$ integers u,v,wu,v,wu,v,w (1≤u,v≤n,−109≤w≤109,u≠v1\leq u,v \leq n, -10^9\leq w \leq 10^9, u \neq v1≤u,v≤n,−109≤w≤109,u=v), indicating that there is an edge between vertex $u$ and vertex $v$ having value $w$ 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 $k$, 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 $k$ 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 $5$, since the maximum value on the cycle is $3$, and the minimum value on the cycle is $-2$, so the maximum range of a cycle is $3-(-2)=5$. It can be shown that there are no cycles with a range larger than $5$.