일회용 스위치

최근 Netwerc Industries에 네트워크 엔지니어로 채용되었다. 첫 업무는 규모가 크고 오래된 사무실 네트워크를 평가하는 것이다. 스위치와 스위치 사이의 케이블로 이루어진 전체 네트워크를 지도로 그려 보니, 일부 스위치는 중복되어 있고 일부는 아예 쓰이지 않는다는 짐작이 들었다. 상사에게 보고하기 전에, 이 주장을 검증하는 프로그램을 만들기로 했다.

주어진 데이터는 네트워크 지도와 각 케이블의 길이이다. 길이가 $\ell$인 케이블을 패킷이 지나는 데 걸리는 시간은

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

이다. 여기서 $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$). $n$은 스위치의 수, $m$은 케이블의 수이다. 스위치는 1부터 $n$까지 번호가 붙어 있다. 이어지는 $m$개의 줄에는 정수 $a$, $b$, $\ell$이 한 줄에 하나씩 주어진다 ($1 \le a, b \le n$, $1 \le \ell \le 10^9$). 이는 스위치 $a$와 $b$를 잇는 길이 $\ell$의 케이블을 뜻한다. 같은 두 스위치를 잇는 케이블은 최대 한 개이며, 스위치를 자기 자신과 잇는 케이블은 없다. 모든 스위치 쌍 사이에는 경로가 존재한다.

첫 줄에 정수 $k$를 출력한다. $k$는 스위치 1에서 스위치 $n$으로 가는 최적 경로에 절대 포함될 수 없는 스위치의 개수이다. 다음 줄에는 그러한 스위치 $k$개의 번호를 오름차순으로 출력한다.