E - Road Reduction Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

AtCoder 王国には都市 1,2,\ldots,N の N 個の都市と、道路 1,2,\ldots,M の M 本の道路があります。
道路 i は都市 A_i と B_i を双方向に結び、距離は C_i です。
どの都市間もいくつかの道路を通って行き来することができます。

財政難である王国は、どの都市間もいくつかの道路を通って行き来できるという条件を満たすように N-1 本の道路を保守し、それ以外の道路を廃道にすることにしました。

保守する道路のみを通って都市 1 から都市 i へ移動するときの距離を d_i とするとき、保守する道路の選び方であって、d_2+d_3+\ldots+d_N を最小化するようなものを 1 つ出力してください。

制約

  • 2 \leq N \leq 2\times 10^5
  • N-1 \leq M \leq 2\times 10^5
  • 1 \leq A_i < B_i \leq N
  • i\neq j のとき、(A_i,B_i)\neq(A_j,B_j)
  • 1\leq C_i \leq 10^9
  • どの都市間もいくつかの道路を通って行き来することができる
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

出力

保守するような道路の番号を空白区切りで出力せよ。出力の順序は問わない。
答えが複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

3 3
1 2 1
2 3 2
1 3 10

出力例 1

1 2

保守する道路の選び方と d_i の値は次のようになります。

  • 道路 1,2 を保守するとき、d_2=1, d_3=3
  • 道路 1,3 を保守するとき、d_2=1, d_3=10
  • 道路 2,3 を保守するとき、d_2=12, d_3=10

よって、道路 1,2 を保守するときに d_2+d_3 が最小になります。

入力例 2

4 6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1

出力例 2

3 1 2

Score : 500 points

Problem Statement

The Kingdom of AtCoder has N cities called City 1,2,\ldots,N and M roads called Road 1,2,\ldots,M.
Road i connects Cities A_i and B_i bidirectionally and has a length of C_i.
One can travel between any two cities using some roads.

Under financial difficulties, the kingdom has decided to maintain only N-1 roads so that one can still travel between any two cities using those roads and abandon the rest.

Let d_i be the total length of the roads one must use when going from City 1 to City i using only maintained roads. Print a choice of roads to maintain that minimizes d_2+d_3+\ldots+d_N.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • N-1 \leq M \leq 2\times 10^5
  • 1 \leq A_i < B_i \leq N
  • (A_i,B_i)\neq(A_j,B_j) if i\neq j.
  • 1\leq C_i \leq 10^9
  • One can travel between any two cities using some roads.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

Print the indices of roads to maintain, in arbitrary order, with spaces in between.
If multiple solutions exist, you may print any of them.

Sample Input 1

3 3
1 2 1
2 3 2
1 3 10

Sample Output 1

1 2

Here are the possible choices of roads to maintain and the corresponding values of d_i.

  • Maintain Road 1 and 2: d_2=1, d_3=3.
  • Maintain Road 1 and 3: d_2=1, d_3=10.
  • Maintain Road 2 and 3: d_2=12, d_3=10.

Thus, maintaining Road 1 and 2 minimizes d_2+d_3.

Sample Input 2

4 6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1

Sample Output 2

3 1 2