A Intensidade de Tráfego

Existem n cidades, ligadas entre si por m estradas. Cada estrada representa uma rota de transporte e possui um valor de intensidade de tráfego , que indica o nível de congestionamento.

O seu objetivo é, para cada cidade i, encontrar o menor congestionamento de trânsito possível no percurso da cidade 1 até à cidade i. Define-se o congestionamento de um percurso como o valor máximo de intensidade de tráfego ao longo desse trajeto.

Entrada

A primeira linha contém dois inteiros, n e m, separados por espaço (), que representam o número de cidades e o número de estradas, respetivamente.

Nas m linhas seguintes, cada linha contém três inteiros e , separados por espaço (), que descrevem uma estrada entre as cidades e com intensidade de tráfego .

Saída

Apresente uma única linha contendo n-1 inteiros separados por espaço, em que o i-ésimo inteiro representa o menor congestionamento de trânsito no percurso da cidade 1 até à cidade i+1.

Exemplos