Contest Duration: ~ (local time) (300 minutes) Back to Home

Time Limit: 2 sec / Memory Limit: 1024 MB

### 注意

この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

### 問題文

あなたは、二本の塔を結ぶ橋を何本か建設して、どの大きな塔から別のどの大きな塔へも何本かの橋を渡って到達できるようにしたい。(小さい塔はどのように扱ってもよい。)

### 制約

• 2 \leqq N \leqq 30
• 1 \leqq M \leqq 5
• 0 \leqq x_i, y_i \leqq 1,000
• 0 \leqq X_i, Y_i \leqq 1,000
• 1 \leqq c_i, C_i \leqq 3
• 入力中の値はすべて整数である。

### 入力

N M
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N
X_1 Y_1 C_1
X_2 Y_2 C_2
:
X_M Y_M C_M


### 入力例 1

3 1
0 0 1
0 1 1
1 0 1
1 1 1


### 出力例 1

2.000000000000


1 番目の大きな塔と 2 番目の大きな塔、1 番目の大きな塔と 3 番目の大きな塔をそれぞれ直接結ぶべきである。合計コストは 1 + 1 = 2 となる。

### 入力例 2

3 1
0 10 1
10 0 2
10 20 3
10 10 1


### 出力例 2

210.000000000000


### Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

### Problem Statement

There are N large towers and M small towers built on a two-dimensional coordinate plane. The i-th large tower (1 \leq i \leq N) has the coordinate (x_i, y_i) and the color c_i, and the i-th small tower (1 \leq i \leq N) has the coordinate (X_i, Y_i) and the color C_i. Here, the color of a tower is given as an integer, where 1, 2, 3 stand for red, green, blue, respectively. There may be multiple towers at the same coordinates.

You want to construct some bridges connecting two towers so that any large tower can be reached from any other large tower using some number of bridges. (The small towers can be treated in any way you like.)

The cost needed to construct a bridge connecting two towers is equal to the Euclidean distance between them, multiplied by 10 if the colors of the towers are different. (The cost does not depend on the sizes of the towers. Also, we do not consider the crossing of bridges.)

Find the minimum total cost needed to achieve your objective.

### Constraints

• 2 \leq N \leq 30
• 1 \leq M \leq 5
• 0 \leq x_i, y_i \leq 1000
• 0 \leq X_i, Y_i \leq 1000
• 1 \leq c_i, C_i \leq 3
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N M
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N
X_1 Y_1 C_1
X_2 Y_2 C_2
:
X_M Y_M C_M


### Output

Print a real number representing the minimum total cost needed to achieve the objective. Your output is considered correct if the absolute or relative error from the judge's output is at most 10^{-6}.

### Sample Input 1

3 1
0 0 1
0 1 1
1 0 1
1 1 1


### Sample Output 1

2.000000000000


We should directly connect the first and second large towers, then the first and third large towers, for a total cost of 1 + 1 = 2.

### Sample Input 2

3 1
0 10 1
10 0 2
10 20 3
10 10 1


### Sample Output 2

210.000000000000


We should connect the small tower to each of the large towers, for a total cost of 10 + 10 \times 10 + 10 \times 10 = 210.