Dado un grafo ponderado no dirigido, determine para cada arista el coste mínimo del árbol de expansión si esta debe incluirse en el árbol de expansión. Puede asumir que el grafo es conexo y simple, y que cada arista aparece como máximo una vez en él.

Entrada

• La primera línea tiene dos enteros ~n~ y ~m~: el número de nodos y aristas. Los nodos están numerados ~1,2,\dots,n~.
• Las siguientes ~m~ líneas describen las aristas. Cada línea tiene tres enteros ~a, b, w~: hay una arista entre los nodos ~a~ y ~b~ con peso ~w~.

Salida

Para cada arista en el orden de entrada, imprima el coste mínimo del árbol de expansión cuando se incluye.

Restricciones

• ~1 \leq n \leq 10^5~
• ~1 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~
• ~1 \leq w \leq 10^9~

Ejemplo de Entrada

5 6
1 2 4
1 3 2
2 4 2
3 4 1
3 5 4
4 5 3

Ejemplo de Salida

10
8
8
8
9
8