h2. Restrictii

* $3 ≤ N ≤ 1019$
* $3 ≤ M ≤ 200 019$
* $3 ≤ K ≤ 1019$
* se garanteaza corectitudinea datelor de intrare
* intre oricare doua cabane exista cel mult o poteca
* vor exista cel putin $K$ drumuri de la cabana $1$ la cabana $N$
* cabana $1$ are altitudinea cea mai mare, cabana $N$ are altitudinea cea mai mica

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. pitici.in |_. pitici.out |

| 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
| 6 6 7

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

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

...

== include(page="template/taskfooter" task_id="pitici") ==