P17002 [NWERC 2019] 无用交换机 / Disposable Switches

译自 [Northwestern Europe Regional Contest (NWERC) 2019](http://2019.nwerc.eu)。

你最近被 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$ 个整数，表示这些未使用交换机的编号，按递增顺序输出。

【数据规模与约定】 - $2\le n\le 2000$。 - $1\le m\le 10^4$。 - $1\le a,b\le n$，$1\le \ell\le 10^9$。 - 任意一对交换机之间至多有一根网线。 - 没有自环。 - 保证任意两台交换机之间都有路径。