Octagon est responsable de nombreuses installations d’importance stratégique, comme des silos à missiles, des radars, des cantines, des bureaux pour les anciens combattants, des entrepôts d’uniformes, … Il est primordial de sécuriser le réseau de connexions entre ces installations, mais il faut aussi minimiser la menace pesant sur ce réseau. Pour chaque route à double sens reliant des installations différentes, un coefficient de menace d’attaque (couramment appelé le coefficient) a été déterminé. Johnny, récemment embauché par Octagon, peut calculer, même au milieu de la nuit, un sous-ensemble de routes qui minimise la somme des coefficients tout en permettant de se déplacer entre toute paire d’installations ; nous appelons route clé une route appartenant à au moins un tel sous-ensemble.

Cependant, rien n’est acquis : les coefficients peuvent changer. Dans le cadre de l’évaluation annuelle, Octagon a décidé de calculer, pour chaque route, la plus grande valeur de $x$ telle que, lorsque son coefficient est fixé à $x$ (et que tous les autres coefficients restent inchangés), cette route soit une route clé. Cette tâche a été confiée à Johnny, qui ne peut se tromper dans une affaire aussi importante.

Entrée

La première ligne de l’entrée contient deux entiers $n$ et $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$), séparés par une seule espace, indiquant respectivement le nombre d’installations supervisées par Octagon et le nombre de routes à double sens entre elles. Les installations sont numérotées par les entiers naturels consécutifs de $1$ à $n$.

Chacune des $m$ lignes suivantes contient trois entiers $a$, $b$ et $c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$), séparés par une seule espace, décrivant une route à double sens entre les installations $a$ et $b$ de coefficient $c$. Toute paire non ordonnée $\{a,b\}$ apparaît au plus une fois.

Les routes existantes permettent toujours de se déplacer entre deux installations quelconques.

Sortie

Vous devez écrire $m$ lignes, une par route de l’entrée, dans le même ordre que dans l’entrée. Sur la ligne correspondant à une route, écrivez un entier naturel : la valeur maximale telle qu’après avoir changé le coefficient de cette route en cette valeur (en laissant les autres coefficients inchangés), cette route soit une route clé. Si cette valeur dépasse $10^9$ ou peut être arbitrairement grande, écrivez $10^9$.

Exemples

Entrée 1

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

Sortie 1

3
3
3
2
8
20
1000000000

Remarque

Le réseau routier de l’exemple est le suivant :