本题没有可用的提交语言。

描述

在比特兰有许多洞穴。这是其中一个洞穴的地图：

比特兰的所有洞穴都具有以下属性：

• 所有的洞室和通道都在同一水平面上。
• 任意两条通道都不会相互交叉。
• 一些洞室位于外圈。它们被称为外洞室。
• 所有其他洞室位于外圈内部，被称为内洞室。
• 有一个通往洞穴的入口，通向其中一个外洞室。
• 每个洞室恰好有三条通道通向三个不同的其他洞室。如果一个洞室是外洞室，那么其中两条通道通向圆圈上相邻的两个外洞室，恰好有一条通道通向一个内洞室。
• 连接外洞室的通道被称为外通道，其余的通道被称为内通道。
• 可以仅使用内通道从一个洞室走到另一个洞室，但如果我们允许每个内通道最多只走一次，那么只有一种走法。
• 并非所有通道的通行难度都相同。它们被分为两组：容易的和困难的。

现在决定向公众开放所有洞穴。为了确保游客在洞穴中能够“顺畅”且安全地通行，游客应该沿着预先标记的路线行走，并且恰好访问这个洞穴的每个洞室一次。唯一的例外是入口洞室，每个游览路线都从这里开始并结束，你被允许恰好访问这个洞室两次。游览路线应该适合普通游客，并且包含尽可能少的难走的通道。

示例： 考虑图中所示的洞穴。入口洞室是$1$号洞室。虚线通道是难走的通道。路线$1, 5, 4, 6, 8, 7, 2, 3$根本不包含难走的通道。最后一个洞室，即1号洞室，是隐含的，未列出。

任务

编写一个程序，该程序：

• 从标准输入读取一个洞穴的描述。
• 找到一条通过洞穴的路线，该路线从入口洞室开始并结束于入口洞室，让游客仅访问所有其他洞室一次，并且包含尽可能少的难走的通道。
• 将结果写入标准输出。

输入

第一行有两个整数$n$，$k$（由单个空格分隔）。整数$n$，$3 < n \leq 500$，是洞穴中所有洞室的数量，$k$是所有外洞室的数量，$k \geq 3$。洞室从$1$到$n$编号。$1$号洞室是入口洞室。$1$号、$2$号、……、$k$号洞室是外洞室。它们不一定按此顺序出现在外圈上。

接下来的$3n / 2$行包含通道的描述。每个描述由三个整数$a$，$b$，$c$组成，由单个空格分隔。整数$a$和$b$是通道两端洞室的编号。整数$c$等于$0$或$1$，其中$0$表示该通道容易通过，$1$表示该通道难通过。

输出

你的程序应该在标准输出的第一行写入一个由$n$个整数组成的序列，这些整数由单个空格分隔；该序列必须以$1$（入口洞室）开头。接下来的$n - 1$个整数应该是计算出的路线上的连续洞室。

输入数据 1

8 5
1 3 0
3 2 0
7 3 1
7 2 0
8 7 0
1 8 0
6 8 0
6 4 0
6 5 1
5 4 0
2 4 0
5 1 0

输出数据 1

1 5 4 6 8 7 2 3

来源

1997年欧洲信息学奥林匹克竞赛（CEOI 1997）