Dağıntı
Fərmanın John n otlaqdan ibarətdir, hər biri cüt-cüt n − 1 ikitərəfli yollarla birləşdirilib. Həmçinin, hər hansı bir otlaqdan digərinə yolun olduğu məlumdur.
Əgər yollardan biri bloklanarsa, ferma iki hissəyə bölünür; hər bir hissə öz daxilində əlaqəli qalır, lakin bir-biri ilə əlaqəsi kəsilir. Buna görə də, Fərman m əlavə yollar tikir, hər biri müsbət tam ədəd uzunluğuna malikdir və 10^9-dan çox deyil. İnəklər mümkün olduğu müddətcə ilkin yollardan istifadə edirlər.
Əgər ilkin yollardan biri bloklanarsa, ferma əlaqəsiz olur və Fərman əlavə yollardan birini seçir ki, fermanın əlaqəsini bərpa etsin, belə ki, inəklər yenidən hər hansı bir otlaqdan digərinə gedə bilsinlər.
Hər bir ilkin yol üçün, Fərmana yenidən tikilmiş yollardan ən qısa uyğun yolu müəyyən etməyə kömək edin.
Giriş məlumatları
Birinci sətir n (2 ≤ n ≤ 50000) və m (1 ≤ m ≤ 50000) ehtiva edir. Sonrakı n − 1 sətir hər bir ilkin yolu tam ədədlərlə p q təsvir edir, burada p ≠ q − bu yolla birləşdirilmiş otlaqlar (aralıqda 1..n). Qalan m sətir hər bir əlavə yolu üç tam ədədlə p, q, r təsvir edir, burada r bu yolun uzunluğudur. Hər hansı iki otlaq arasında bir yoldan çox olmur.
Çıxış məlumatları
Hər bir n − 1 ilkin yol üçün, girişdə göründükləri sıraya görə, ilkin yolun bloklanması nəticəsində fermanın əlaqəsini bərpa edəcək ən qısa "əvəzləyici" yolun uzunluğunu çıxarın. Əgər belə bir yol mövcud deyilsə, -1 çıxarın.