4556 - 사다리타기

Time Limit: 1s Memory Limit: 128MB

Submissions: 246 Solved: 64
Description

0부터 n-1까지의 번호가 부여된 n개의 세로줄에 가로줄을 그린 다음 사다리타기를 하려고 한다.

사다리타기란, 맨 위에서부터 시작하여 세로줄을 따라 내려가다가 가로줄을 만나면 가로줄을 타고 옆으로 이동한 다음 다시 내려가는 게임이다.

가로줄을 그리고 난 후 각 시작점에 0부터 n-1까지의 번호를 부여했을 때 사다리타기 결과를 출력해보자.

(한 점에서 두 개 이상의 가로줄이 그려지는 경우는 없다.)

Input

* Line 1 : 사다리의 갯수 n (1 ≤ n ≤ 100)

* Line 2 : 사다리 선 갯수 m (1 ≤ m ≤ 10000)

* Line 3 ~ m+2 : 연결할 두 사다리 번호 a, b와 선의 높이 h ( 0 ≤ a, b ≤ n-1, a≠b , 1 ≤ h ≤ 10000)

Output

* Line 1~n: 0~n-1번째 시작점에서 출발했을 때 도착하게 되는 지점을 출력한다.

Sample Input
5
6
0 1 3
0 1 2
2 3 3
1 2 1
3 4 1
3 4 2
Sample Output
0
3
1
2
4
Hint
0 1 2 3 4
├┤├┤│
1 0 3 2 4
├┤│├┤
0 1 3 4 2
│├┤├┤
0 3 1 2 4