Î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 de 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ța

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 pitici.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 trei 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 pitici.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 și precizări

• 2 < N < 1020
• 2 < M < 200.020
• 1 < K < 1020
• 0 < lungimea unei poteci < 1020
• Se garantează corectitudinea datelor de intrare.
• Între oricare două 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ă.

Exemplu:

pitici.in

9 11 3
1 2 1
1 4 1
2 3 1
3 7 4
7 9 1
4 6 2
4 5 1
5 8 4
6 8 1
6 7 2
8 9 2

pitici.out

6 6 7

Explicație

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.