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.

Va trebui să analizezi harta prezentată şi să determini *timpul minim* în care poţi ajunge şi nava aleasa (cea cu *capacitatea minimă* pentru care se obţine acest timp), precum şi drumul pe care îl vei alege. Deoarece timpul minim poate fi un număr foarte mare, nu trebuie să afli decît ultimele 6 cifre ale sale, ca să poţi verifica la destinaţie corectitudinea calculelor tale.

h2. Cerinţă
 
Va trebui să analizezi harta prezentată şi să determini *timpul minim* în care poţi ajunge şi nava aleasa (cea cu *capacitatea minimă* pentru care se obţine acest timp), precum şi drumul pe care îl vei alege. Deoarece timpul minim poate fi un număr foarte mare, nu trebuie să afli decît *ultimele 6 cifre* ale sale, ca să poţi verifica la destinaţie corectitudinea calculelor tale.

h2. Date de intrare

Fişierul de intrare $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ţ
* 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
* î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