The Traffic Intensity
There are
n cities, connected by m roads. Each road represents a transportation route and has a traffic intensity value Your task is to find, for each city
i, the minimum possible transit congestion from city 1 to city i. The transit congestion of a path is defined as the maximum traffic intensity along that path.Input
The first line contains two space-separated integers,
n and m (), representing the number of cities and the number of roads, respectively.The next
m lines each contain three space-separated integers Output
Output a single line containing
n-1 space-separated integers, where the i-th integer represents the minimum possible transit congestion from city 1 to city i+1.Examples
Input | Output |
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