walk (IATI junior)
Time limit: 1.5 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: sorting, graph theory, longest path, dynamic programming

# Task 3. WALK ⏳1,5 sec. 512 MB

## Who doesn't love walks?

The map of Shumen can be represented as $N$ crossroads, numbered with the integers from 1 to $N$ with $M$ bidirectional streets between them, numbered with the integers from 1 to $M$. Every street connects a pair of different crossroads, and there isn't a pair of crossroads that are connected by two different streets. One could get from any crossroad to any other by traversing through the given streets.

Kyusho and his dog Bobby were having a night walk right before yesterday's party. They traversed all the $M$ streets at least once in the walk. Bobby, the dog, is exceptionally intelligent but has problems memorizing the order of the traversed streets and that's why it memorized them rather chaotically and sometimes even contradictory. For example, it is possible that for some street the dog has memorized that is was traversed at moment 10 but there is no street that was memorized being traversed at moment 9. Formally, Bobby, the dog, has memorized that the $i$-th street between crossroads $a_i$ and $b_i$ was traversed at moment $c_i$.

In the morning, Kyusho realized that he also has problems remembering last night and wanted to recall the traversed crossroads from the walk as best as possible. To do this, he will take another walk, starting from his hotel in crossroad 1. As he does not want to get lost, he will traverse the streets in a way, that every subsequently passed street has been traversed at a later moment than the previous one (according to the memories of Bobby, the dog), or in other words, $c_{next} > c_{current}$. It is possible to pass a crossroad more than once.

Kyusho wants his new walk to contain as many streets as possible and end at some crossroad, but he still hasn't decided where he will stop. So, he desires to know the longest walk to every crossroad following the rules of moving from the previous paragraph. Please, help him by writing a program **walk**, which finds the inquired maximal lengths with regards to the number of passed streets.

#### Input

The first line of the standard input contains the two integers $N$ and $M$ – the count of the crossroads and the count of the streets between them. Each of the rest $M$ lines contains three integers – $a_i$, $b_i$ and $c_i$, which describe a street between the crossroads with numbers $a_i$ and $b_i$, traversed at moment $c_i$ (according to the memories of Bobby, the dog).

#### Output

The only line of the standard output should contain $N$ integers, each separated by a space – the maximal lengths of walks from crossroad 1 to all crossroads 1, 2, ..., $N$. If there is no possible walk to one of them, you should print 0 as the maximal length of a walk to this crossroad.

## Constraints

- $2 \le N \le 10^5$
- $1 \le M \le 10^6$
- $1 \le a_i, b_i \le N$, $a_i \ne b_i$
- $1 \le c_i \le 10^9$

## Subtasks

| Subtask | Points | Required subtasks |   N         |   M                  |   Other constraints                  |
| :-------: | :----: | :---------------: | :----------: | :-------------------: | :------------------------------------: |
|    1    |    0   |         -         |      -      |         -         |     The example test.             |
|    2    |   10   |         1         | $\le 10$   |      $\le 15$      |                 -                |
|    3    |    7   |         -         | $\le 10^5$  |       $= N - 1$        |                 -                |
|    4    |   29   |       1, 2        | $\le 10^3$  |      $\le 10^4$      |                 -                |
|    5    |   27   |         1         | $\le 10^5$  | $\le 3 \times 10^5$ | $c_i \neq c_j \text{ for } i \neq j$ |
|    6    |    7   |       1 - 5       | $\le 10^5$  | $\le 3 \times 10^5$ |                 -                |
|    7    |   14   |       1, 5        | $\le 10^5$  |      $\le 10^6$      | $c_i \neq c_j \text{ for } i \neq j$ |
|    8    |    6   |       1 - 7       | $\le 10^5$  |      $\le 10^6$      |                 -                |

*The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.*

## Example

| Input                                                                                                                | Output          | Explanation of the example                                                                                                                                                                                                                                                                                            |
| :--------------------------------------------------------------------------------------------------------------------- | :--------------: | :----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| 8 12<br>1 4 9<br>1 6 4<br>1 5 1<br>3 4 11<br>3 5 10<br>5 6 2<br>6 2 6<br>2 8 7<br>5 8 8<br>7 8 5<br>5 7 14<br>3 7 12 | 3 3 6 7 8 2 7 4 | Illustration of the streets and crossroads:<br>![](_page_1_Picture_1.jpeg)<br>Optimal walk to crossroad with number 3 is the following: 1 5 2 6 6 2 7 8 8 5 10 3.<br>Notice, that when we are at crossroad 8 in the walk, we cannot continue to crossroad 7 because the moment of that street is 5 but we have come from a street with moment 7. |

Starter code:

Grader code:

Setup script:

Evaluation script: