2077 年，人工智能刚刚解决了超图着色的最后一个难题，理论计算机科学系那些刚失业的研究人员被一位古怪的亿万富翁 Melon Usk 聘请，为 Hyperloop 复合体开发软件——这是一个超高速城际连接系统。

由于水位上升，地球上仅存的陆地是一个单一的岛屿，其海岸线上坐落着 $n$ 个幸存城市，为了方便起见，我们按它们沿海岸线出现的顺序将其命名为 $1, 2, \dots, n$。Melon 拥有环绕岛屿运行的渡轮，即连接城市 $i$ 和 $i+1$（对于 $1 \le i < n$）以及城市 $n$ 和 $1$。他还拥有连接某些非相邻城市对的 Hyperloop 连接。

剩下的唯一工作就是设计计算城市间最短路径的软件；在测试版本中，它仅支持从 $1$ 到 $n$ 的旅行。

这个任务看起来可能很简单：毕竟，软件需要同时考虑这两种类型的连接，而且在城市 $1$ 和 $n$ 之间已经存在直接的渡轮连接，但这不一定是最快的路线！更糟糕的是，可能存在多条最短路径。在这种情况下，系统应该优先选择包含尽可能长的城市间连接的路径（单段旅程持续时间越长，乘客在旅途中购买 Melon 高价咖啡的可能性就越大）。形式上，为了比较总长度相同的路径，应列出路径中各连接的长度（包括重复项），将每个序列按非递增顺序排序，并选择字典序最大的一个。

给定环绕岛屿的渡轮和 Hyperloop 连接的描述，找出从城市 $1$ 到城市 $n$ 的最优路径。在比较路径时，两种连接同等对待。所有连接均为双向。

请注意，此任务的内存限制较低，为 64MB。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 600$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ ($3 \le n \le 100\,000, n \le m \le 300\,000$)，分别表示城市数量和连接数量。

接下来的 $m$ 行，每行包含三个整数 $u_i, v_i, d_i$ ($1 \le u_i \neq v_i \le n, 1 \le d_i \le 50\,000$)，依次表示：由给定双向连接相连的城市，以及通行所需的时间。

在输入给出的连接中，会出现 $(1, 2), (2, 3), \dots, (n, 1)$，对应于渡轮连接。

任意一对城市之间最多只有一条连接。

所有测试用例中的城市总数不超过 $400\,000$。所有测试用例中的连接总数不超过 $800\,000$。

输出格式

对于每个测试用例，第一行输出一个整数 $k$，表示最优路径中的城市数量。第二行输出 $k$ 个不同的整数，表示路径上依次经过的城市编号。

所选路径应从城市 $1$ 开始，在城市 $n$ 结束，并且是问题描述中定义的最优路径。

如果存在多条最优路径，输出其中任意一条即可。

样例

样例输入 1

2
4 6
1 2 1
1 3 2
2 3 1
2 4 2
3 4 1
1 4 4
6 11
1 2 9
2 3 12
3 4 3
4 5 5
5 6 10
6 1 22
2 4 9
3 6 1
4 6 5
2 5 2
3 5 8

样例输出 1

3
1 2 4
5
1 2 5 3 6

说明

在第一个样例测试中，从城市 $1$ 到城市 $4$ 的最小距离为 $3$，由三条路径实现：$1 \to 2 \to 4$，$1 \to 3 \to 4$ 和 $1 \to 2 \to 3 \to 4$。根据问题描述的定义，前两条路径优于第三条，因为字典序 $(2, 1) > (1, 1, 1)$。前两条路径中的任意一条都是正确答案。直接路径 $1 \to 4$ 不被考虑，因为其总长度为 $4$。

在第二个样例测试中，最小距离的路径为 $1 \to 2 \to 5 \to 3 \to 6$ 和 $1 \to 2 \to 5 \to 4 \to 3 \to 6$。第一条路径是最优的，因为比较它们排序后的长度得到 $(9, 8, 2, 1) > (9, 5, 3, 2, 1)$。