Peste nouă mări şi nouă ţări, într-o mare împărăţie, prinţesa Alexandra s-a îndrăgostit foarte tare de Făt-Frumos, cel mai puternic şi mai viteaz bărbat. Din nefericire pentru ea, în urmă cu mulţi ani, în timpul unei lupte împotriva lui Gefghev tiranicul împarat din vremea aceea, lui Făt-Frumos i-a scăzut foarte mult karma şi din această cauză nu mai are voie să se apropie de instituţiile publice. Astfel, de fiecare dată când cei doi vor să se întâlnească, Făt-Frumos îi trimite Alexandrei un bileţel printr-un porumbel călător. Pe bileţel, Făt-Frumos scrie cea mai apropiată staţie de tren faţă de pădurea în care se ascunde acesta. Aşadar, Alexandra trebuie să se ducă la cea mai apropiată staţie de tren şi de acolo să ajungă în staţia indicată de Făt-Frumos. Aici intervine mama Alexandrei care nu-şi va lăsa fata să îşi abandoneze responsabilităţile princiare chiar atât de uşor. De fiecare dată când fata vrea să se întâlnească cu Făt-Frumos, trebuie să-i spună mamei timpul exact pe care îl va face trenul din staţia de plecare până la staţia indicată de Făt-Frumos. Alexandra cunoaşte foarte bine sistemul feroviar din împărăţie şi ştie următoarele:
• Între oricare două staţii există un drum unic care nu trece prin aceeaşi staţie de două ori.
• Pentru oricare două staţii unite direct printr-o linie de cale ferată, Alexandra cunoaşte distanţa dintre staţii şi viteza maximă cu care un tren poate circula pe această linie.
Cerinţă
Alexandra nu se simte în largul ei când trebuie să facă calcule, mai cu seamă că împaraţia este foarte mare şi calculele pot deveni destul de complicate. Din această cauză vă roagă să scrieţi un program care primeşte configuraţia sistemului feroviar şi răspunde unor întrebări de forma x y v, cu următoarea semnificaţie: “Cât timp îi va fi necesar unui tren care poate merge cu viteza maximă v, să ajungă din staţia x în staţia y?”.
Date de intrare
Pe prima linie a fişierului de intrare trenuri1.in se află două numere naturale N şi M, reprezentând numărul de staţii din sistemul feroviar, respectiv numărul de întrebări pe care le pune Alexandra. Pe următoarele N–1 linii, se află câte 4 numere x y d v având semnificaţia că există o linie de cale ferată directă de la staţia x la staţia y de lungime d, care nu poate fi parcursă cu o viteză mai mare decât v. Următoarele M linii conţin câte trei numere: x y v, reprezentând întrebările puse de Alexandra, având semnificaţia descrisă în enunţ.
Date de ieşire
În fişierul trenuri1.out se vor afla M numere, câte unul pe linie, reprezentând răspunsurile la întrebările Alexandrei cu o precizie de trei zecimale.
Restricţii
• 3 < N, M < 100 000
• Lungimea unui drum va fi un număr natural mai mic decât 100 000.
• Viteza maximă pe care o poate atinge un tren este un număr natural mai mic sau egal decât 1000.
• Pentru fiecare întrebare se ştie că trenul va merge pe drumul minim dintre staţia x şi staţia y.
• Oricare tren merge cu minimul dintre viteza maximă pe care o poate atinge şi viteza maximă admisă pe linia de cale ferată pe care se află.
• Diferenţa maximă cu care rezultatul final poate varia faţă de cel corect este de 0.001.
Exemple
trenuri1.in
trenuri1.out
Explicaţii
4 2
1 2 4 2
1 3 6 5
3 4 2 10
1 4 7
2 3 4
1.485
3.500
Primul tren va parcurge drumul dintre staţia 1 şi staţia 3 cu viteza 5, iar drumul de la staţia 3 la staţia 4 cu viteza 7. Astfel, timpul total va fi: 6/5 + 2/7 = 1.485714286