Octagon está a cargo de muchas instalaciones de importancia estratégica, como silos de misiles, radares, comedores, oficinas de veteranos, almacenes de uniformes, … Es de suma importancia proteger la red de conexiones entre estas instalaciones, pero, por otro lado, debe minimizarse la amenaza a esta red. Para cada carretera bidireccional que conecta instalaciones distintas se determinó el Coeficiente de Amenaza de Ataque (llamado coloquialmente el coeficiente). Johnny, contratado recientemente por Octagon, puede calcular incluso en plena noche un subconjunto de carreteras que minimice la suma de los coeficientes y siga permitiendo desplazarse entre cualquier par de instalaciones; llamamos carretera clave a una carretera que pertenece al menos a uno de esos subconjuntos.

Sin embargo, nada puede darse por sentado: los coeficientes pueden cambiar. Como parte de la evaluación anual, Octagon decidió calcular para cada carretera el mayor valor de $x$ tal que, al fijar su coeficiente en $x$ (y dejar todos los demás coeficientes como estaban), esta carretera sea clave. La tarea fue asignada a Johnny, que no puede equivocarse en un asunto tan importante.

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$), separados por un solo espacio, que indican respectivamente el número de instalaciones supervisadas por Octagon y el número de carreteras bidireccionales entre ellas. Las instalaciones están numeradas con números naturales consecutivos del $1$ al $n$.

En cada una de las siguientes $m$ líneas hay tres enteros: $a$, $b$ y $c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$), separados por un solo espacio, que describen una carretera bidireccional entre las instalaciones $a$ y $b$ con coeficiente $c$. Cada par no ordenado $\{a,b\}$ aparece como máximo una vez.

Las carreteras existentes siempre permiten desplazarse entre cualesquiera dos instalaciones.

Salida

Debes imprimir $m$ líneas, una por cada carretera de la entrada, en el mismo orden en que aparecen. En la línea correspondiente a una carretera, debes imprimir un número natural: el valor máximo tal que, tras cambiar el coeficiente de esa carretera a dicho valor (y mantener los demás coeficientes sin cambios), esta sea una carretera clave. Si este valor supera $10^9$ o puede ser arbitrariamente grande, debes imprimir $10^9$.

Ejemplos

Entrada 1

6 7
1 2 2
2 3 1
3 4 0
1 4 3
3 5 20
4 5 8
3 6 14

Salida 1

3
3
3
2
8
20
1000000000

Nota

La red de carreteras del ejemplo es la siguiente: