Description

给定一个有$n$ 个节点、$m$ 条边的无向图，每条边都涂有$1$种颜色。求节点$1$到$n$ 的一条路径，使得经过的边数最少，在此前提下，经过边的颜色序列最小。可能有自环与重边。输入保证至少存在一条连接节点$1$和$n$的路径。

Format

Input

输入共$m +1$行。第1行包含两个整数：$n$和$m$。之后的$m$行，每行都包含3个整数$ai 、bi 、ci$，表示在$ai 、bi$之间有一条颜色为$ci$的路径。

Output

输出共两行，第1行包含正整数$k$，表示节点$1$到$n$至少需要经过$k$ 条边。第2行包含$k$ 个由空格隔开的正整数，表示节点$1$到$n$依次经过的边的颜色。

Samples

4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

2
1 3

输出样例解释：节点$1$到$4$至少经过两条边：$1→3$，颜色为$1$（最后输入的那条）；$3→4$，颜色为$3$。数据范围：$2≤n ≤105$，$1≤m ≤105$，$1≤ci ≤109$ ，对于任意$i ∈[1,m ]$，都有$1≤ai ,bi ≤n$ 。对于两个长度为$k$ 的序列$a$ 和$b$，若存在$i ∈[1,k ]$使$ai <bi$ ，且对于任意$j∈[1,i )$都有$aj =bj$ ，则$a <b$ 。

来源

UVA1599