h2. Date de intrare

Pe prima linie a fisierului de intrare $pitici.in$ sunt scrise trei numere naturale $N M K$ separate prin cate un spatiu cu semnificatia din enunt. Urmatoarele $M$ linii contin cate $3$ numere $a b c$ separate prin cate un spatiu, cu semnificatia ca exista poteca de la cabana $a$ la cabana $b$ de lungime $c$, cabana $a$ avand o altitudine mai mare decat cabana $b$.

Pe prima linie a fisierului de intrare pitici.in sunt scrise trei numere naturale $N M K$ separate prin cate un spatiu cu semnificatia din enunt. Urmatoarele $M$ linii contin cate $3$ numere $a b c$ separate prin cate un spatiu, cu semnificatia ca exista poteca de la cabana $a$ la cabana $b$ de lungime $c$, cabana $a$ avand o altitudine mai mare decat cabana $b$.

h2. Date de iesire

FiÅŸierul de iesire $pitici.out$ va contine o singura linie pe care vor fi scrise $K$ numere naturale separate prin cate un spatiu. Al $i$-lea numar reprezinta lungimea drumului ales de piticul $i$.

...

h2. Restrictii