34598번 - Rim 서브태스크다국어

문제

Jedna mala, ali predivna, otočna država sastoji se od $N$ otoka, označenih brojevima od 1ドル$ do $N$. Otoci su povezani s $N-1$ mostova tako da je moguće doći od bilo kojeg otoka do bilo kojeg drugog otoka koristeći mostove. Svaki most povezuje neka dva otoka i ima određenu nosivost. Nosivost definiramo kao najveći broj kilograma koji most može izdržati.

To znači da preko određenog mosta smijemo poslati pošiljke koje imaju najviše onoliko kilograma kolika je i nosivost tog mosta. Na primjer, ako je nosivost određenog mosta 1000ドル$ kilograma, onda smijemo slati pošiljke težine 100ドル,ドル 300ドル,ドル 950ドル$ i 1000ドル$ kilograma, ali ne možemo slati pošiljke težine npr. 1001ドル$ i 2000ドル$ kilograma.

Vlada te države je počela planirati obnovu mostova. Za cijenu jednog eura, Vlada može povećati nosivost jednog mosta za jedan kilogram. Uočite da nije moguće povisiti nosivost za npr. 0ドル.5$ kilograma, samo za prirodan broj kilograma. Pozvali su tebe da pomogneš tj. da im odgovoriš na $Q$ pitanja oblika: “Koliko najviše kilograma može imati pošiljka koju šaljemo od otoka s oznakom $C$ do otoka s oznakom $D,ドル ako za obnovu imamo proračun od $M$ eura?”. Možeš li im pomoći?

입력

U prvom retku su prirodni brojevi $N,ドル $Q$ (2ドル ≤ N ≤ 100,円 000,ドル 1ドル ≤ Q ≤ 100,円 000$).

U idućih $N-1$ redova su prirodni brojevi $A_i,ドル $B_i$ i $T_i$. (1ドル ≤ A_i, B_i ≤ N,ドル $A_i \ne B_i,ドル 1ドル ≤ T_i ≤ 10^9$), oznake otoka koje povezuje $i$-ti most i njegova nosivost.

U idućih $Q$ redova su prirodni brojevi $C_i,ドル $D_i$ i $M_i$ (1ドル ≤ C_i, D_i ≤ N,ドル 1ドル ≤ M_i ≤ 10^9$), brojevi iz teksta zadatka.

출력

U $Q$ redova ispiši po jedan cijeli broj, odgovor na svako pitanje redom u kilogramima.

제한

서브태스크

노트

Opis prvog probnog primjera: U prvom upitu može se utrošiti 4ドル$ eura na prvi most, 3ドル$ eura na treći most i jedan euro na zadnji most. U drugom upitu možemo u drugi most utrošiti 3ドル$ eura, u četvrti 6ドル$ eura i 4ドル$ eura u zadnji most.