* 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

* $1 ≤ K ≤ 10 000$

* $t{~i~} ≤ 1 000, c{~i~} ≤ 1 000, 1 ≤ i ≤ M$

* $2 ≤ t{~i~} ≤ 1 000, 1 ≤ c{~i~} ≤ 1 000, 1 ≤ i ≤ M$

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

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

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

| 7 8 6
1 4
6 5 9 8 7 10
1 2 7 8
1 4 14 9
1 5 3 1
2 3 1 2
2 7 7 1
3 4 2 2
4 6 4 1
5 6 3 7
| 000014 8
1 2 3 4

|
h3. Explicaţie

...

$2$ este planeta cheie (prin dispariţia ei nu s-ar mai putea ajunge în $7$). Alegem nava de capacitate $8$ şi putem parcurge $1 – 2$. În $2$ alimentăm cu combustibil şi parcurgem şi restul drumului: $2 – 3 – 4$. Rezultă un timp total de $7 * 1 * 2 = 14$.
 
Alegând drumul $1 – 4$, am fi obţinut acelaşi timp, dar am fi avut nevoie de o navă de capacitate mai mare. !problema/misiune?misiune.png!

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