* 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

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

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

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

h2. Exemplu