Eşti un super-erou în anul 2222 şi ai primit următoarea misiune: pornind de pe planeta ta natală, *Ilop*, va trebui să încerci să ajungi pe *Acinhet*, altfel lumea va fi distrusă de o armată de monştri verzi.

Pentru a putea îndeplini acest lucru, îţi este dată harta universului: N *planete* şi M *conexiuni* interplanetare *bidirecţionale* ce leagă aceste planete între ele, fiecare necesitând un *timp de parcurgere*  şi o anumită *cantitate de combustibil* pentru a fi parcursă.

Pentru a putea îndeplini acest lucru, îţi este dată harta universului: $N$ *planete* şi $M$ *conexiuni* interplanetare *bidirecţionale* ce leagă aceste planete între ele, fiecare necesitând un *timp de parcurgere*  şi o anumită *cantitate de combustibil* pentru a fi parcursă.

Deoarece te deplasezi cu viteza luminii, regulile cu care eşti obişnuit nu mai funcţionează, iar timpul total se va obţine prin *înmulţirea* timpilor de pe parcurs.
Există unele *planete cheie* pe care îţi poţi alimenta nava. O planetă cheie are proprietatea că o dată cu dispariţia ei (din cauza unei catastrofe de proporţii, să zicem), s-ar pierde legatură între cel puţin două planete între care acum există drum (*un drum* este format din una sau mai multe conexiuni interplanetare).

La plecare eşti pus să îţi alegi o navă, din cele K disponibile, pentru fiecare dintre ele fiind specificată capacitatea rezervorului. Urmăreşti să poţi parcurge drumul de la Ilop la Acinhet în *timp minim*, dar, de asemenea, fiind vremuri de criză, şi să alegi nava cu capacitatea rezervorului minimă care îţi permite acest lucru. Nu uita că îţi poţi reumple rezervorul pe parcurs, dacă ajungi pe o planetă cheie.

La plecare eşti pus să îţi alegi o navă, din cele $K$ disponibile, pentru fiecare dintre ele fiind specificată capacitatea rezervorului. Urmăreşti să poţi parcurge drumul de la Ilop la Acinhet în *timp minim*, dar, de asemenea, fiind vremuri de criză, şi să alegi nava cu capacitatea rezervorului minimă care îţi permite acest lucru. Nu uita că îţi poţi reumple rezervorul pe parcurs, dacă ajungi pe o planetă cheie.

h2. Cerinţă

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

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

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

* pe a 2-a linie numerele prin care sunt codificate planeta de start şi planeta destinaţie

* pe a 3-a linie {*K*} numere întregi capi reprezentând capacităţile navelor dintre care poţi alege

* pe a 3-a linie $K$ numere întregi capi reprezentând capacităţile navelor dintre care poţi alege

* în continuare, {*m*} linii de forma: {*x{~i~} y{~i~} t{~i~} c{~i~}*}, cu semnficaţia: de la {*x{~i~}*} la {*y{~i~}*} (şi de la {*y{~i~}*} la {*x{~i~}*}) se poate ajunge în {*t{~i~}*} unităţi de timp folosind o cantitate {*c{~i~}*} de combustibil

* în continuare, $m$ linii de forma: $x{~i~} y{~i~} t{~i~} c{~i~}$, cu semnficaţia: de la $x{~i~}*} la {*y{~i~}$ (şi de la $y{~i~}$ la $x{~i~}$) se poate ajunge în $t{~i~}$ unităţi de timp folosind o cantitate $c{~i~}$ de combustibil

h2. Date de ieşire
Datele de ieşire se vor scrie în fişierul $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

* 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

* pe a 2-a linie numerele planetelor ce se află pe drumul parcurs de la *start* la *destinaţie*

* $cap{~i~} ≤ 1 000, 1 ≤ i ≤ K$

* Fie $T$ timpul minim de parcurgere a drumului. Capacitatea rezervorului este minimă dacă pentru o navă de capacitate mai mică am obţine un timp de parcurgere mai mare decât $T$.
 
* Se garantează că pentru toate testele se va putea alege o navă cu care să poată fi parcurs drumul.
 
* Dacă există mai mult decât un drum ce respectă condiţiile cerute, se poate afişa oricare dintre acestea.
 
* Atenţie! Doar pentru *70%* din teste, timpul minim de parcurgere se va încadra într-un unsigned $long long int$.
 

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