다채로운 경로

칼레이도스탄에는 도시가 $n$개 있고, 이 도시들은 양방향 도로 $m$개로 연결되어 있다. 도시는 1번부터 $n$번까지 번호가 매겨져 있다. 각 도로에는 색상 값이라는 정수가 하나씩 있다.

케이누는 도시 1에서 도시 $n$까지 이동하려고 한다. 그는 최단 경로, 즉 도로 수가 가장 적은 경로를 택하려고 한다. 최단 경로가 여러 개라면, 그중에서 경로에 있는 도로들의 색상 값 최댓값과 최솟값의 차이가 가장 큰 다채로운 경로를 택하려고 한다. 케이누가 그런 경로를 찾도록 도와라.

첫 줄에는 도시 수와 도로 수를 뜻하는 두 정수 $n$, $m$이 주어진다 ($2 \le n \le 10^5$; $1 \le m \le 2 \cdot 10^5$).

다음 $m$개 줄의 $i$번째 줄에는 $i$번째 도로가 잇는 두 도시의 번호 $v_i$, $u_i$와 그 도로의 색상 값 $c_i$가 주어진다 ($1 \le v_i, u_i \le n$; $v_i \neq u_i$; $0 \le c_i \le 10^9$).

같은 두 도시를 잇는 도로는 최대 하나다. 어느 도시에서든 도로를 따라 다른 모든 도시로 이동할 수 있다는 것이 보장된다.

첫 줄에 필요한 경로의 도로 수 $k$를 한 정수로 출력한다.

둘째 줄에는 경로 위의 도시 번호 $c_0, c_1, \ldots, c_k$를 $k+1$개의 정수로 출력한다 ($1 \le c_i \le n$; $c_0 = 1$; $c_k = n$).

예시 테스트에서 필요한 경로는 도로 3개로 이루어지며, 이 도로들의 색상 값 최댓값과 최솟값의 차이는 $8-2=6$이다.