pitici

Î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 $x_1 \ x_2 \ ... \ x_p$ cu proprietatea că $x_1=1, x_p=N$ şi între oricare două cabane consecutive pe drum $x_i$ şi $x_{i+1}$ există o potecă ce merge în vale (adică altitudinea cabanei $x_i$ este mai mare decât altitudinea cabanei $x_{i+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 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 $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 iesire

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 < 1 \ 020$
• $2 < M < 200 \ 020$
• $1 < K < 1 \ 020$
• $0 <$ lungimea unei poteci $< 1 \ 020$
• 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ă.

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$.