h2. Date de intrare

Datele de intrare se vor citi din fişierul $misiune.in$:

Fişierul de intrare $misiune.in$:

* pe prima linie {*N*}, {*M*} şi {*K*}, separate de câte un spaţiu, cu semnificaţia din enunţ

h2. Date de ieşire

Datele de ieşire se vor scrie în fişierul $misiune.out$:

În fişierul de ieşire $misiune.out$ ...

*   pe prima linie *TMin6* şi *CapMin*, reprezentând *ultimele 6 cifre* ale timpul minim de parcurgere şi capacitatea minimă a navei cu care se poate obţine acest timp

h2. Restricţii

* pe a 2-a linie numerele planetelor ce se află pe drumul parcurs de la *start* la *destinaţie*
 
 
h2. Restricţii şi precizări
 
* $2 &le N &le 1 000$
 
* $1 &le M &le 30 000$
 
* $1 &le K &le 10 000*
 
* $t~i~ &le 1 000, c~i~ &le 1 000, 1 &le i &le M
 
* cap~i~ &le 1 000, 1 &le i &le K

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

h2. Exemplu