Interrupción#10392
Farmer John se enjorgullece de administrar una granja bien conectada. La granja consta de pastos conectados por n - 1 caminos bidireccionales, cada uno de longitud unitaria. Farmer John observa que, utilizando una secuencia apropiada de estos caminos, es posible viajar desde cualquier pasto hasta cualquier otro pasto.
Aunque la granja de FJ está conectada, le preocupa lo que podría suceder si uno de los caminos se bloquea: esto dividiría su granja en dos conjuntos disjuntos de pastos, de modo que las vacas podrían viajar dentro de cada conjunto pero no entre los conjuntos. Por lo tanto, FJ construye caminos bidireccionales adicionales, cada uno con una longitud entera positiva que no excede 10^9. Las vacas siguen usando solamente los caminos originales, a menos que uno de ellos se bloquee.
Si uno de los caminos originales se bloquea, la granja se divide en dos partes disjuntas, y FJ elige uno de los caminos adicionales como reemplazo para reconectar estas dos partes, de modo que las vacas puedan nuevamente viajar desde cualquier pasto hasta cualquier otro pasto.
Para cada uno de los caminos originales, ayuda a FJ a elegir el camino de reemplazo adecuado más corto.
La primera línea contiene dos enteros y m~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 5 \cdot 10^4). Cada una de las siguientes n - 1 líneas describe un camino original y contiene dos enteros y q~(1 \le p, q \le n, p \ne q) — los pastos conectados por este camino. Cada una de las siguientes líneas describe un camino adicional y contiene tres enteros , , y , donde y son los pastos que conecta y es su longitud. Cualquier par de pastos está conectado por como máximo un camino.
Para cada uno de los n - 1 caminos originales, en el orden en que aparecen en la entrada, imprime la longitud del camino de reemplazo adecuado más corto que reconectaría la granja si este camino original se bloqueara. Si no existe un reemplazo adecuado, imprime .
Ejemplo 1