L'Intensità del Traffico

Ci sono n città, collegate da m strade. Ogni strada rappresenta una rotta di trasporto e ha un valore di intensità di traffico che indica il livello di congestione.

Il tuo compito è di determinare, per ogni città i, la minima possibile congestione di transito dalla città 1 alla città i. La congestione di transito di un percorso è definita come il valore massimo di intensità di traffico che si incontra lungo tale percorso.

Input

La prima riga contiene due numeri interi separati da spazio, n e m (), che rappresentano rispettivamente il numero di città e il numero di strade.

Le successive m righe contengono ciascuna tre interi separati da spazio e (), che indicano una strada tra le città e con intensità di traffico .

Output

Bisogna stampare una singola riga contenente n-1 interi separati da spazio, dove l'i-esimo intero rappresenta la minima congestione di transito possibile dalla città 1 alla città i+1.

Esempi