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.

h2. Restricţii şi precizări

* $2 &le N &le 1 000$

* $2 ≤ N ≤ 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$

* $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$

* cap ~i~ &le 1 000, 1 &le i &le K$

h2. Exemplu