Interruzione#10392
Farmer John va fiero di gestire una fattoria ben connessa. La fattoria è costituita da pascoli collegati da n - 1 sentieri bidirezionali, ciascuno di lunghezza unitaria. Farmer John nota che, utilizzando un'opportuna sequenza di questi sentieri, è possibile spostarsi da qualsiasi pascolo a qualsiasi altro pascolo.
Sebbene la fattoria di FJ sia connessa, egli si preoccupa di cosa potrebbe accadere se uno dei sentieri venisse bloccato: questo dividerebbe la sua fattoria in due insiemi disgiunti di pascoli, in modo che le mucche potrebbero spostarsi all'interno di ciascun insieme ma non tra gli insiemi. Pertanto, FJ costruisce sentieri bidirezionali aggiuntivi, ciascuno con una lunghezza intera positiva non superiore a 10^9. Le mucche continuano a utilizzare solo i sentieri originali, a meno che uno di essi non venga bloccato.
Se uno dei sentieri originali viene bloccato, la fattoria si divide in due parti disgiunte, e FJ sceglie uno dei sentieri aggiuntivi come sostituto per ricollegare queste due parti, in modo che le mucche possano nuovamente spostarsi da qualsiasi pascolo a qualsiasi altro pascolo.
Per ciascuno dei sentieri originali, aiuta FJ a scegliere il sentiero sostitutivo più corto adatto.
La prima riga contiene due interi e m~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 5 \cdot 10^4). Ciascuna delle successive n - 1 righe descrive un sentiero originale e contiene due interi e q~(1 \le p, q \le n, p \ne q) — i pascoli collegati da questo sentiero. Ciascuna delle successive righe descrive un sentiero aggiuntivo e contiene tre interi , e , dove e sono i pascoli che collega e è la sua lunghezza. Ogni coppia di pascoli è collegata da al più un sentiero.
Per ciascuno degli n - 1 sentieri originali, nell'ordine in cui compaiono nell'input, stampa la lunghezza del sentiero sostitutivo più corto adatto che ricollegherebbe la fattoria se questo sentiero originale venisse bloccato. Se non esiste un sostituto adatto, stampa .
Esempio 1