The Traffic Intensity

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.

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

To check your solution you need to sign in