우회 노선

델프트에서 암스테르담까지 버스로 이동한다. 가는 길의 모든 교차로에는 암스테르담까지 가는 최단 경로 방향을 가리키는 표지판이 서 있다. 그런데 이 버스는 표지판이 가리키는 도로로 한 번도 들어가지 않는다.

이런 버스 노선이 존재하는지 판정하라. 버스 노선은 델프트에서 출발해 암스테르담에서 끝나고, 같은 교차로를 두 번 지나지 않는다. 노선 위의 교차로 가운데 암스테르담을 뺀 모든 교차로에서, 버스가 이어서 지나는 도로는 그 교차로의 표지판이 가리키는 도로와 달라야 한다.

도로망은 단순하고 연결된 무방향 그래프이고, 모든 교차로에서 암스테르담까지 가는 최단 경로는 유일하다. 교차로의 표지판은 그 최단 경로의 첫 번째 도로를 가리킨다.

첫 줄에 교차로의 수 $n$ ($2 \le n \le 10^5$)과 도로의 수 $m$ ($1 \le m \le 10^6$)이 공백으로 구분되어 주어진다. 교차로 번호는 $0$부터 $n-1$까지이며, 델프트가 $0$번, 암스테르담이 $1$번이다.

다음 $m$개 줄에 도로가 한 줄에 하나씩 세 정수 $a_i$, $b_i$ ($0 \le a_i, b_i < n$, $a_i \ne b_i$), $d_i$ ($0 \le d_i \le 500000$)로 주어진다. 교차로 $a_i$와 교차로 $b_i$를 잇는 도로이고, 어느 방향으로 지나든 길이는 $d_i$다.

조건을 만족하는 노선이 없으면 impossible을 출력한다.

있으면 노선을 한 줄에 출력한다. 먼저 노선이 지나는 교차로의 수 $k$를 출력하고, 이어서 버스가 지나는 순서대로 교차로 번호 $p_0, \dots, p_{k-1}$을 출력한다. 여기서 $p_0 = 0$이고 $p_{k-1} = 1$이다.

조건을 만족하는 노선이 여러 개일 수 있다. 그중 지나는 교차로의 수가 가장 적은 노선을 출력한다. 그런 노선이 여러 개면 수열 $p_0, \dots, p_{k-1}$이 사전순으로 가장 앞서는 노선을 출력한다.