問題文

N個の街があり、0, 1, 2, ..., N-1と番号がついています。最初、これらの街の間に道はなく、街と街を行き来することはできません。

道の候補がM個あります。i番目の道を建設するには建設費がc_i円かかりますが、建設すると街u_iと街v_iを双方向に結ぶ道ができ、行き来できるようになります。

M個の道の候補からいくつか選んで建設し、ある街から別の任意の街へ道をたどって到達できるようにしたいです。そのように道を選んで建設するために必要な建設費の最小値を求めてください。

制約

• 入力は全て整数である
• 1 \leq N \leq 10^5
• 0 \leq M \leq 10^5
• 0 \leq u_i, v_i \lt N (0 \leq i \lt M)
• u_i \neq v_i (0 \leq i \lt M)
• 0 \leq c_i \leq 10^9 (0 \leq i \lt M)
• ある街から別の任意の街へ道をたどって到達できるようにする道の選び方が必ず存在する

入力例 1

5 7
0 1 10
0 4 30
1 2 10
1 4 20
2 3 30
4 2 20
4 3 10

出力例 1

50