Problem Q
遠回り

去年のProgramming Contestが終わった後、あなたはまだデルフトにいた。今年もまた参加するためには、アムステルダムにバスで行く必要がある。

移動の間あなたが窓の外を見ていると、アムステルダムへの方向が書かれた標識を見つけた。驚いたことに、バスは標識で示された方向に向かっていない！ そこで、あなたは考えた。どの交差点でも目的地に向かう標識に従わずに目的地までたどれるルートがあるのではないかと。

しかし、友人は信じていない様子で、そんなことは無理だと考えている。 この条件を満たすルートを見つけることができるか。 注意点として、バスルートは同じ交差点を2度通ってはならない。

また、各交差点に置かれている標識は、アムステルダムまでの最短距離となる方向を示している。 交差点と道路とで作られるグラフは単純で連結しており、すべての交差点からアムステルダムへの最適なルートは単一であると仮定してよい。

入力

• 先頭行は $2$ つの整数で、交差点の数 $n$ は ($2 \le n \le 10^5$)、交差点間を結ぶ道（すべて双方通行）の数 $m$ は ($1 \le m \le 10^6$)。 交差点には $0$ から $n-1$ までの番号が付けられている。デルフトは交差点 $i=0$ 、アムステルダムは交差点 $i=1$ である。

• その後 $m$ 行は道路を表す。

  • $3$ つの整数で、この道路の起終点となる交差点 $a_ i$, $b_ i$ は $0 \leq a_ i, b_ i < n$ かつ $a_ i \ne b_ i$、この道路の道のり $d_ i$ は $0 \le d_ i \leq 500000$。

出力

以下のいずれかを出力する。

• デルフトからアムステルダムの、与えられた条件を満たす経路（存在する場合）。

  • 経路は1行内に経路数 $k$、その後に $k$ 個の経路上の交差点 $p_ i$ 。なお、$p_0 = 0$, $p_{k-1}=1$。

• 条件を満たす経路が存在しない場合、“impossible”。

4 5
0 2 5
2 1 5
0 3 10
3 1 20
3 2 5

3 0 3 1

4 3
0 1 10
1 2 20
2 3 30

impossible

7 9
0 1 800
6 2 300
2 3 75
3 4 80
4 5 50
4 1 100
1 6 35
0 2 120
0 3 100

2 0 1