În vârful muntelui Acrom trăiesc pe timpul verii K pitici, numerotaţi de la 1 la K.
Pe munte există N cabane, aflate la altitudini diferite, legate între ele prin M poteci. Cabana piticilor este numerotată cu 1, iar cabana de la poalele muntelui cu N.
Fiindcă iarna este prea frig, piticii se mută în cabana de la poalele muntelui, unde este mai cald. Piticii sunt disciplinaţi şi coboară de pe munte în ordinea crescătoare a numerelor lor. Pentru a nu fi acuzaţi de lipsă de personalitate, fiecare pitic alege drumul cel mai scurt până jos, drum diferit de fiecare dintre drumurile alese de piticii ce au coborât înaintea lui. Un drum al unui pitic este o succesiune de cabane x1 x2 ... xp cu proprietatea că x1=1, xp=N şi între oricare două cabane consecutive pe drum xi şi xi+1 există o potecă ce merge în vale (adică altitudinea cabanei xi este mai mare decât altitudinea cabanei xi+1). Două drumuri sunt diferite dacă există cel puţin o cabană ce aparţine unuia dintre drumuri şi nu aparţine celuilalt. Lungimea unui drum este suma lungimilor potecilor ce leagă cabanele situate pe acest drum.
Cerinţă
Scrieţi un program care să determine lungimea drumului ales de fiecare pitic, drum ce respectă condiţiile din enunţ.
Date de intrare
Pe prima linie a fişierului de intrare pitici1.in sunt scrise trei numere naturale N M K separate prin câte un spaţiu cu semnificaţia din enunţ. Următoarele M linii conţin câte 3 numere a b c separate prin câte un spaţiu, cu semnificaţia că există potecă de la cabana a la cabana b de lungime c, cabana a având o altitudine mai mare decât cabana b.
Date de ieşire
Fişierul de ieşire pitici1.out va conţine o singură linie pe care vor fi scrise K numere naturale separate prin câte un spaţiu. Al i-lea număr reprezintă lungimea drumului ales de piticul i.
Restricţii
2 < N < 1020
2 < M < 200 020
1 < K < 1020
0 < lungimea unei poteci < 1020
Se garantează corectitudinea datelor de intrare.
Între oricare 2 cabane există cel mult o potecă.
Vor exista cel puţin K drumuri diferite de la cabana 1 la cabana N.
Cabana 1 are altitudinea cea mai mare, iar cabana N cea mai mică.
Primul pitic va alege drumul format din cabanele 1 4 6 7 9, drumul având lungimea 6.
Al doilea va alege drumul 1 4 6 8 9, tot de lungime 6.
Ultimul pitic va alege drumul 1 2 3 7 9 de lungime 7.