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
Entrada | Saída |
5 5
1 2 5
1 3 2
4 5 10
4 3 6
1 5 9 | 5 2 6 9 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB