The Traffic Intensity

There are n cities, connected by m roads. Each road represents a transportation route and has a traffic intensity value $w_i$ 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 ($1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5$), representing the number of cities and the number of roads, respectively.

The next m lines each contain three space-separated integers $a_i, b_i$, and $w_i$ ($1 ≤ a_i, b_i ≤ n, 1 ≤ w_i ≤ 10^9$), representing a road between cities $a_i$ and $b_i$ with traffic intensity $w_i$.

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