Kesinti#10392
Farmer John, iyi bağlantılı bir çiftlik işletmekten gurur duymaktadır. Çiftlik, her biri birim uzunluğunda olan n - 1 çift yönlü yol ile birbirine bağlanmış otlaktan oluşmaktadır. Farmer John, bu yolların uygun bir sırasını kullanarak herhangi bir otlaktan herhangi bir diğer otlağa gidilebileceğini fark eder.
FJ'nin çiftliği bağlantılı olsa da, yollardan birinin tıkanması durumunda ne olabileceğinden endişelenmektedir: bu, çiftliğini birbirinden ayrık iki otlak kümesine bölecektir, öyle ki inekler her kümenin içinde seyahat edebilir ama kümeler arasında seyahat edemez. Bu nedenle FJ, her birinin 10^9'u aşmayan pozitif tam sayı uzunluğu olan tane ek çift yönlü yol inşa eder. İnekler, bu yollardan biri tıkanmadığı sürece yalnızca orijinal yolları kullanmaya devam eder.
Orijinal yollardan biri tıkanırsa, çiftlik iki ayrık parçaya bölünür ve FJ, ek yollardan birini bu iki parçayı yeniden birleştirecek bir yedek olarak seçer, böylece inekler tekrar herhangi bir otlaktan herhangi bir diğer otlağa seyahat edebilir.
Orijinal yolların her biri için, FJ'ye en kısa uygun yedek yolu seçmesinde yardımcı olun.
İlk satır iki tam sayı içerir: ve m~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 5 \cdot 10^4). Sonraki n - 1 satırın her biri bir orijinal yolu tanımlar ve bu yolun bağladığı otlakları belirten iki tam sayı ve q~(1 \le p, q \le n, p \ne q) içerir. Sonraki satırın her biri bir ek yolu tanımlar ve üç tam sayı , ve içerir; burada ve bu yolun bağladığı otlaklar, ise bu yolun uzunluğudur. Herhangi bir otlak çifti en fazla bir yol ile bağlıdır.
Orijinal n - 1 yolun her biri için, girişte göründükleri sırayla, bu orijinal yol tıkanırsa çiftliği yeniden bağlayacak en kısa uygun yedek yolun uzunluğunu yazdırın. Eğer uygun bir yedek yol yoksa, yazdırın.
Örnek 1