Disposable Switches

You were recently hired by Netwerc Industries as a network engineer. Your first task is to assess their large, dated office network. You have mapped the network, which consists of switches and the cables between them. You suspect that some switches are redundant and that others are not used at all. Before you present this to your boss, you decide to write a program to test the claim.

The data consists of the network map and the length of each cable. A packet sent across a cable of length $\ell$ takes time

$\frac{\ell}{v} + c$

where $v$ is the propagation speed of the cable and $c$ is the overhead of transmitting the packet on and off the cable. The values of $v$ and $c$ are unknown. You only know that they are real numbers with $v > 0$ and $c \ge 0$, and that they are the same for all cables. Network routing ensures that a packet takes an optimal path, meaning a path that minimizes the total transit time.

Given the network map and the cable lengths, determine which switches can never be part of an optimal path from switch 1 to switch $n$, no matter what the values of $v$ and $c$ are.

The first line has two integers $n$ and $m$ ($2 \le n \le 2\,000$, $1 \le m \le 10^4$), the number of switches and cables. The switches are numbered 1 to $n$. Each of the next $m$ lines has three integers $a$, $b$, and $\ell$ ($1 \le a, b \le n$, $1 \le \ell \le 10^9$), describing a cable of length $\ell$ between switches $a$ and $b$. At most one cable connects any pair of switches, and no cable connects a switch to itself. There is a path between every pair of switches.

First output a line with an integer $k$, the number of switches that can never be part of an optimal path from switch 1 to switch $n$. Then output a line with the $k$ indices of these switches in increasing order.