Problem D
Disposable Switches

Picture by Ted Sakshaug on Flickr, cc by

The data you have gathered consists of the map of the network, as well as the length of each cable. While you do not know the exact time it takes to send a network packet across each cable, you know that it can be calculated as $\ell / v + c$, where

• $\ell $ is the length of the cable,

• $v$ is the propagation speed of the cable, and

• $c$ is the overhead of transmitting the packet on and off the cable.

You have not been able to measure $v$ and $c$. The only thing you know about them is that they are real numbers satisfying $v > 0$ and $c \ge 0$, and that they are the same for all cables. You also know that when a network packet is being transmitted from one switch to another, the network routing algorithms will ensure that the packet takes an optimal path—a path that minimises the total transit time.

Given the map of the network and the length of each cable, determine which switches could never possibly be part of an optimal path when transmitting a network packet from switch $1$ to switch $n$, no matter what the values of $v$ and $c$ are.

Input

The input consists of:

• One line with two integers $n$, $m$ ($2 \leq n \leq 2\, 000$, $1 \leq m \leq 10^4$), the number of switches and the number of cables in the network. The switches are numbered from $1$ to $n$.

• $m$ lines, each with three integers $a$, $b$ and $\ell $ ($1 \leq a, b \leq n$, $1\leq \ell \leq 10^9$), representing a network cable of length $\ell $ connecting switches $a$ and $b$.

There is at most one cable connecting a given pair of switches, and no cable connects a switch to itself. It is guaranteed that there exists a path between every pair of switches.

Output

First output a line with an integer $k$, the number of switches that could never possibly be part of an optimal path when a packet is transmitted from switch $1$ to switch $n$. Then output a line with $k$ integers, the indices of the $k$ unused switches, in increasing order.

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