User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Description

在某個偏僻的地區,存在著一個國家,
這個國家裡有 $n$ 個城鎮,為了方便起見,這邊用 $1, 2, \dots, n$ 來表示每個城鎮。

城鎮與城鎮之間以道路相連,每個城鎮都至少會有一條道路直達別的城鎮,並且兩個城鎮之間至多只會有一條直達的道路。

現在有一個旅人想到這個國家來旅遊,但是這個旅人的個性非常懶惰,
若是他現在在城市 $x$,則當他要移動到下一個城市時,
只會移動到 $x$ 可以到達的所有城市中,距離城市 $x$ 最近的城市(不包含 $x$)。

然後因為這個旅人很懶,所以他請你告訴他,當他在城市 $x$ 時,下一個城市應該要移動到哪。

Input Format

第一行包含了 $2$ 個正整數 $n, m$,分別代表城鎮數量與道路數量;
接下來 $m$ 行都由 $3$ 個整數 $u, v, len$ 組成,
代表城市 $u$ 與 $v$ 中有一條長度為 $len$ 的直達道路。

  • $2 \leq n \leq 2 \cdot 10^5$
  • $1 \leq m \leq min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5)$
  • $1 \leq u, v \leq n, u \neq v$
  • $1 \leq len \leq 10^9$

Output Format

請輸出 $n$ 個整數 $x_1, x_2, \dots, x_n$,
$x_i$ 代表當旅人待在城市 $i$ 時,他下次應該要移動到城市 $x_i$。

若是有兩組以上的答案,輸出任意一種即可。

Sample Input 1

3 3
1 2 1
2 3 2
1 3 3

Sample Output 1

2 1 2

Sample Input 2

5 4
1 3 5
3 2 9
3 4 8
5 3 1

Sample Output 2

3 3 5 3 3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~12 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1