There are n cities, connected by m roads. Each road represents a transportation route and has a traffic intensity value that indicates its congestion level.

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 , and (), representing a road between cities and with traffic intensity .

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.