F - Transportation Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

AtCoder 国には N 個の島があり、 最初、どの島にも空港・港はなく、どの島の間にも道路はありません。 王である高橋君はこれらの島の間に交通手段を用意することにしました。 具体的には、高橋君は次の操作のうち 1 つを選んで行うことを好きなだけ繰り返す事ができます。

  • 1\leq i\leq N をみたす i を選び、コスト X_i を払って、島 i に空港を建設する。
  • 1\leq i\leq N をみたす i を選び、コスト Y_i を払って、島 i に港を建設する。
  • 1\leq i\leq M をみたす i を選び、コスト Z_i を払って、島 A_i と島 B_i の間を双方向に結ぶ道路を建設する。

高橋君の目標は、任意の相異なる 2 つの島 U, V について、 島 U からはじめて次の行動のうち 1 つを選んで行うことを好きなだけ繰り返す事で、 島 V に到達することができるようにする事です。

  • 島 S,T の両方に空港がある時、島 S から島 T まで移動する。
  • 島 S,T の両方に港がある時、島 S から島 T まで移動する。
  • 島 S,T を結ぶ道路が存在する時、島 S から島 T まで移動する。

高橋君が目標を達成するのに必要な最小コストを求めてください。

制約

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1\leq X_i\leq 10^9
  • 1\leq Y_i\leq 10^9
  • 1\leq A_i<B_i\leq N
  • 1\leq Z_i\leq 10^9
  • i\neq j ならば (A_i,B_i)\neq (A_j,B_j)
  • 入力は全て整数

入力

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

N M
X_1 X_2 \ldots X_N
Y_1 Y_2 \ldots Y_N
A_1 B_1 Z_1
A_2 B_2 Z_2
\vdots
A_M B_M Z_M

出力

高橋君が目標を達成するのに必要な最小コストを出力せよ。

入力例 1

4 2
1 20 4 7
20 2 20 3
1 3 5
1 4 6

出力例 1

16

高橋君は次のように交通手段を建設します。

  • コスト X_1=1 を払って、島 1 に空港を建設する。
  • コスト X_3=4 を払って、島 3 に空港を建設する。
  • コスト Y_2=2 を払って、島 2 に港を建設する。
  • コスト Y_4=3 を払って、島 4 に港を建設する。
  • コスト Z_2=6 を払って、島 1 と島 4 の間を結ぶ道路を建設する。

このとき、目標は達成されており、かかったコストは 16 となります。 コスト 15 以下で目標を達成する方法はないため、16 を出力します。

入力例 2

3 1
1 1 1
10 10 10
1 2 100

出力例 2

3

空港・港・道路のうち、一度も建設されないものがあっても構いません。

入力例 3

7 8
35 29 36 88 58 15 25
99 7 49 61 67 4 57
2 3 3
2 5 36
2 6 89
1 6 24
5 7 55
1 3 71
3 4 94
5 6 21

出力例 3

160

Score : 500 points

Problem Statement

The Republic of AtCoder has N islands. Initially, none of the islands has an airport or harbor, and there is no road between any two of them. Takahashi, the king, will provide some means of transportation between these islands. Specifically, he can do the following operations any number of times in any order.

  • Choose an integer i such that 1\leq i\leq N and pay a cost of X_i to build an airport on island i.
  • Choose an integer i such that 1\leq i\leq N and pay a cost of Y_i to build a harbor on island i.
  • Choose an integer i such that 1\leq i\leq M and pay a cost of Z_i to build a road that bidirectionally connects island A_i and island B_i.

Takahashi's objective is to make it possible, for every pair of different islands U and V, to reach island V from island U when one can perform the following actions any number of times in any order.

  • When islands S and T both have airports, go from island S to island T.
  • When islands S and T both have harbors, go from island S to island T.
  • When islands S and T are connected by a road, go from island S to island T.

Find the minimum total cost Takahashi needs to pay to achieve his objective.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1\leq X_i\leq 10^9
  • 1\leq Y_i\leq 10^9
  • 1\leq A_i<B_i\leq N
  • 1\leq Z_i\leq 10^9
  • (A_i,B_i)\neq (A_j,B_j), if i\neq j.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
X_1 X_2 \ldots X_N
Y_1 Y_2 \ldots Y_N
A_1 B_1 Z_1
A_2 B_2 Z_2
\vdots
A_M B_M Z_M

Output

Print the minimum total cost Takahashi needs to pay to achieve his objective.

Sample Input 1

4 2
1 20 4 7
20 2 20 3
1 3 5
1 4 6

Sample Output 1

16

Takahashi will build the following infrastructure.

  • Pay a cost of X_1=1 to build an airport on island 1.
  • Pay a cost of X_3=4 to build an airport on island 3.
  • Pay a cost of Y_2=2 to build a harbor on island 2.
  • Pay a cost of Y_4=3 to build a harbor on island 4.
  • Pay a cost of Z_2=6 to build a road connecting island 1 and island 4.

Then, the objective will be achieved at a cost of 16. There is no way to achieve the objective for a cost of 15 or less, so 16 should be printed.

Sample Input 2

3 1
1 1 1
10 10 10
1 2 100

Sample Output 2

3

It is not mandatory to build all three types of facilities at least once.

Sample Input 3

7 8
35 29 36 88 58 15 25
99 7 49 61 67 4 57
2 3 3
2 5 36
2 6 89
1 6 24
5 7 55
1 3 71
3 4 94
5 6 21

Sample Output 3

160