MarsX

Time limit: 0.3s Memory limit: 64MB Input: Output:

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 nn peșteri conectate prin mm canale unidirecționale. Misiunea acestora este să ajungă din baza subterană a coloniștilor aflată în galeria 11 în orașul subteran al reptilienilor plasat în galeria nn pentru a distruge rezistența extraterestră.

Știind că fiecare dintre cele mm 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 nn (numărul de galerii) și mm (numărul de canale subterane), apoi mm triplete de forma uu, vv, ww, cu proprietatea că există canal unidirecțional între peștera uu și peștera vv, protejat de exact ww soldați.

Date de ieșire

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

Restricții și precizări

  • Se garantează că există rută optimă între galeriile 11 și nn pentru fiecare test.
  • 1n100 0001 \leq n \leq 100 \ 000;
  • 1m200 0001 \leq m \leq 200 \ 000;
  • 1u,vn1 \leq u, v \leq n;
  • 1w1 000 000 0001 \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

Log in or sign up to be able to send submissions!