L’intensité du trafic
Il y a
n villes, reliées par m routes. Chaque route représente un itinéraire de transport et possède une valeur d’intensité de trafic qui indique son niveau de congestion.Votre tâche consiste à déterminer, pour chaque ville
i, la congestion de transit minimale possible entre la ville 1 et la ville i. La congestion de transit d’un chemin se définit comme la valeur d’intensité de trafic la plus élevée le long de ce chemin.Entrée
La première ligne contient deux entiers séparés par un espace,
n et m (), qui représentent respectivement le nombre de villes et le nombre de routes.Les
m lignes suivantes contiennent chacune trois entiers séparés par un espace et (), indiquant une route reliant les villes et avec une intensité de trafic .Sortie
Affichez sur une seule ligne
n-1 entiers séparés par des espaces. Le i-ième entier correspond à la congestion de transit minimale possible entre la ville 1 et la ville i+1.Exemples
Entrée | Sortie |
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