背景

译自 Northwestern Europe Regional Contest (NWERC) 2019。

题目描述

你最近被 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 2000$, $1\le m\le 10^4$)，分别表示交换机数量和网线数量。交换机编号为 $1$ 到 $n$。
• 接下来 $m$ 行，每行包含三个整数 $a,b,\ell$ ($1\le a,b\le n$, $1\le \ell\le 10^9$)，表示一根长度为 $\ell$、连接交换机 $a$ 和 $b$ 的网线。

任意一对交换机之间至多有一根网线，且没有网线连接某个交换机自身。保证任意两台交换机之间都有路径。

输出格式

第一行输出一个整数 $k$，表示无论如何都不可能出现在从交换机 $1$ 到交换机 $n$ 的最优路径上的交换机数量。

第二行输出 $k$ 个整数，表示这些未使用交换机的编号，按递增顺序输出。

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

2
4 6

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

0

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

1
4

提示

【数据规模与约定】

• $2\le n\le 2000$。
• $1\le m\le 10^4$。
• $1\le a,b\le n$，$1\le \ell\le 10^9$。
• 任意一对交换机之间至多有一根网线。
• 没有自环。
• 保证任意两台交换机之间都有路径。