# 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