MarsX

Pe planeta Marte se desfășoară un intens război între trupele coloniștilor pământeni și triburile autohtone de reptilieni.

Pentru a dobândi controlul decisiv asupra planetei, pământenii au trimis trupe de commando în sistemul de galerii subterane de pe Marte, reprezentat sub forma unei configurații de $n$ peșteri conectate prin $m$ canale unidirecționale. Misiunea acestora este să ajungă din baza subterană a coloniștilor aflată în galeria $1$ în orașul subteran al reptilienilor plasat în galeria $n$ pentru a distruge rezistența extraterestră.

Știind că fiecare dintre cele $m$ canale dintre galerii este protejat de un anumit număr de soldați reptilieni, trupele de commando trebuie să aleagă rutele de deplasare cât mai vulnerabile în fața unui asalt, protejate de un număr minim de inamici.

Se cere să aflați setul de galerii care vor fi obligatoriu traversate de pământeni pe parcursul misiunii, folosind orice rută ce este protejată de un număr minim de inamici.

Date de intrare

Se vor citi de la tastatură valorile $n$ (numărul de galerii) și $m$ (numărul de canale subterane), apoi $m$ triplete de forma $u$, $v$, $w$, cu proprietatea că există canal unidirecțional între peștera $u$ și peștera $v$, protejat de exact $w$ soldați.

Date de ieșire

Se va afișa pe prima linie valoarea $k$ (numărul de galerii care vor fi obligatoriu traversate de coloniști), iar pe următoarea linie cele $k$ galerii în ordine crescătoare.

Restricții și precizări

• Se garantează că există rută optimă între galeriile $1$ și $n$ pentru fiecare test.
• $1 \leq n \leq 100 \ 000$;
• $1 \leq m \leq 200 \ 000$;
• $1 \leq u, v \leq n$;
• $1 \leq w \leq 1 \ 000 \ 000 \ 000$.

Exemplu

stdin

5 6
1 2 3
1 3 4
2 3 1
2 4 5
3 4 1
4 5 8

stdout

4
1 3 4 5