Grammy 有一个简单的连通无向图。每条边上都写有一个权值。请为她选择一个简单环，使得环上权值的极差尽可能大。

环的极差定义为环上权值的最大值与最小值之差。

一个环 $i_1 - e_1 - i_2 - e_2 - \dots - i_k - e_k - i_1$（其中 $e_j$ 是连接图中顶点 $i_j$ 和 $i_{j \pmod k + 1}$ 的某条边）被称为简单环，当且仅当每条边在环中最多出现一次。

为了证明你确实找到了该环，你需要按顺序输出环上的顶点。

保证图中至少存在一个环。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($3 \le n \le m \le 10^5$)，分别表示图的顶点数和边数。

接下来的 $m$ 行，每行包含三个整数 $u, v, w$ ($1 \le u, v \le n, -10^9 \le w \le 10^9, u \neq v$)，表示顶点 $u$ 和顶点 $v$ 之间有一条权值为 $w$ 的边。保证图是连通的，且每对顶点之间最多只有一条边。

输出格式

第一行输出一个整数，表示图中简单环的最大极差。

第二行输出一个整数 $k$，表示环中的边数。不难发现，环中的边数等于环中的顶点数。

最后一行输出 $k$ 个整数，按顺序表示环上的顶点。注意，这些顶点可以重复，因为限制仅为边不能被多次访问。

如果存在多个解，输出其中任意一个即可。

样例

样例输入 1

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

样例输出 1

5
5
1 2 5 4 3

说明

在第一个样例中，环 1-2-5-4-3-1 的极差最大，为 5。因为该环上权值的最大值为 3，最小值为 -2，所以环的极差为 $3 - (-2) = 5$。可以证明不存在极差大于 5 的环。