Pozulma#10392
Farmer John özünün yaxşı əlaqələndirilmiş fermaya sahib olması ilə fəxr edir. Ferma otlaqdan ibarətdir və bunlar hər biri vahid uzunluğa malik n - 1 ikitərəfli yolla birləşdirilib. Farmer John müşahidə edir ki, bu yolların müvafiq ardıcıllığından istifadə edərək istənilən otlaqdan istənilən digər otlağa getmək mümkündür.
FJ-nin fermasının bağlı olmasına baxmayaraq, o, yollardan birinin bağlanması halında nə baş verəcəyindən narahatdır: bu, fermanı iki ayrı otlaq dəstinə bölər, belə ki, inəklər hər dəstin daxilində hərəkət edə bilsələr də, dəstlər arasında hərəkət edə bilməzlər. Buna görə də FJ, hər birinin uzunluğu müsbət tam ədəd olub 10^9-u keçməyən ədəd əlavə ikitərəfli yol tikir. İnəklər, yollardan biri bağlanmayana qədər, yalnız ilkin yollardan istifadə etməyə davam edirlər.
İlkin yollardan biri bağlanarsa, ferma iki ayrı hissəyə bölünür və FJ bu iki hissəni yenidən birləşdirmək üçün əlavə yollardan birini əvəzedici kimi seçir ki, inəklər yenidən istənilən otlaqdan istənilən digər otlağa gedə bilsinlər.
FJ-yə hər bir ilkin yol üçün ən qısa uyğun əvəzedici yolu seçməkdə kömək edin.
Birinci sətirdə iki tam ədəd və m~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 5 \cdot 10^4) verilir. Növbəti n - 1 sətirdən hər biri ilkin yolu təsvir edir və iki tam ədəd və q~(1 \le p, q \le n, p \ne q) ehtiva edir — bu yolla birləşdirilən otlaqlar. Növbəti sətirdən hər biri əlavə yolu təsvir edir və üç tam ədəd , və ehtiva edir, burada və bu yolun birləşdirdiyi otlaqlar, isə onun uzunluğudur. İstənilən otlaq cütü ən çoxu bir yolla birləşdirilib.
n - 1 ilkin yolun hər biri üçün, daxiletmədə göründükləri ardıcıllıqla, həmin ilkin yol bağlanarsa fermanı yenidən birləşdirəcək ən qısa uyğun əvəzedici yolun uzunluğunu çap edin. Əgər uyğun əvəzedici mövcud deyilsə, çap edin.
Nümunə 1