你刚被 Netwerc Industries 聘为网络工程师，你的首要任务是评估他们庞大且陈旧的办公网络。在绘制出整个网络（由网络交换机和它们之间的电缆组成）的地图后，你产生了一个直觉：不仅有些交换机是多余的，甚至有些交换机根本没有被使用！在向老板汇报之前，你决定编写一个程序来验证你的猜想。

你收集到的数据包括网络地图以及每根电缆的长度。虽然你不知道通过每根电缆发送网络数据包的确切时间，但你知道它可以计算为 $\ell/v + c$，其中：

• $\ell$ 是电缆的长度，
• $v$ 是电缆的传播速度，
• $c$ 是在电缆上发送和接收数据包的开销。

你无法测量 $v$ 和 $c$。你唯一知道的是它们是满足 $v > 0$ 和 $c \ge 0$ 的实数，且对于所有电缆，这两个值都是相同的。你还知道，当网络数据包从一个交换机传输到另一个交换机时，网络路由算法会确保数据包走的是一条最优路径——即总传输时间最短的路径。

给定网络地图和每根电缆的长度，请确定无论 $v$ 和 $c$ 的值是多少，哪些交换机在将网络数据包从交换机 $1$ 传输到交换机 $n$ 时，永远不可能成为最优路径的一部分。

输入格式

输入包含：

• 一行，包含两个整数 $n, m$ ($2 \le n \le 2\,000, 1 \le m \le 10^4$)，表示网络中交换机的数量和电缆的数量。交换机编号为 $1$ 到 $n$。
• $m$ 行，每行包含三个整数 $a, b$ 和 $\ell$ ($1 \le a, b \le n, 1 \le \ell \le 10^9$)，表示连接交换机 $a$ 和 $b$ 的长度为 $\ell$ 的网络电缆。

给定的一对交换机之间最多只有一根电缆，且没有电缆连接交换机自身。保证每对交换机之间都存在路径。

输出格式

首先输出一行，包含一个整数 $k$，表示在将数据包从交换机 $1$ 传输到交换机 $n$ 时，永远不可能成为最优路径一部分的交换机数量。然后输出一行，包含 $k$ 个整数，即这 $k$ 个未使用交换机的索引，按升序排列。

样例

样例输入 1

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

样例输出 1

2
4 6

样例输入 2

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

样例输出 2

0

样例输入 3

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

样例输出 3

1
4