阿Q所在的城市可以抽象成为一个有 $n(1 \le n \le 20000)$个点和 $m(1 \le m \le 50000)$ 条无向边的地图。

阿Q住在 1 号点，他想进行一次环城市旅游。他从 1 点出发，每次沿着和 1 点相连的边中最短的边到下一个城市（如果有很多个最短的边，选择编号最小的走），到达下一个城市以后，还是沿着和这个城市相连的最短边走到下一个点（如果有很多个最短的边，选择编号最小的走），一直这样走下去，直到要走到一个已经走过的，就结束这次旅行。

输入格式

输入第一行两个整数 n，m，两数之间以一个空格分隔。

接下来 m 行，每行输入三个整数 $u,v(1 \le u, v \le n, u \ne v)$，表示有一条连接 u 和 v 长度为 w(w在整型范围内) 的无向边，相邻两数之间以一个空格分隔。

输出格式

输出一行若干个整数，依次表示阿Q旅行经过的点，每两个数中间用一个空格隔开。

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 travel.in，输出文件为 travel.out

样例输入

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

样例输出

1 4 3