在某個偏僻的地區,存在著一個國家,
這個國家裡有 $n$ 個城鎮,為了方便起見,這邊用 $1, 2, \dots, n$ 來表示每個城鎮。
城鎮與城鎮之間以道路相連,每個城鎮都至少會有一條道路直達別的城鎮,並且兩個城鎮之間至多只會有一條直達的道路。
現在有一個旅人想到這個國家來旅遊,但是這個旅人的個性非常懶惰,
若是他現在在城市 $x$,則當他要移動到下一個城市時,
只會移動到 $x$ 可以到達的所有城市中,距離城市 $x$ 最近的城市(不包含 $x$)。
然後因為這個旅人很懶,所以他請你告訴他,當他在城市 $x$ 時,下一個城市應該要移動到哪。
第一行包含了 $2$ 個正整數 $n, m$,分別代表城鎮數量與道路數量;
接下來 $m$ 行都由 $3$ 個整數 $u, v, len$ 組成,
代表城市 $u$ 與 $v$ 中有一條長度為 $len$ 的直達道路。
請輸出 $n$ 個整數 $x_1, x_2, \dots, x_n$,
$x_i$ 代表當旅人待在城市 $i$ 時,他下次應該要移動到城市 $x_i$。
若是有兩組以上的答案,輸出任意一種即可。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~12 | 無特別限制 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 |