题目描述

小明正在参加一场爆破工作。人们在地面上放置了 $n$ 个爆炸魔法阵，第 $i$ 个魔法阵的圆心坐标为 $(x_i, y_i)$，半径为 $r_i$。如果两个魔法阵相交，则它们可以一起引爆；如果两个魔法阵不相交，则可以再使用一条魔法回路将它们的边缘连接起来。小明想知道最少需要布置总长度多长的魔法回路才能使得所有的魔法阵可以一起引爆？

输入格式

输入共 $n + 1$ 行。

第一行为一个正整数 $n$。

后面 $n$ 行，每行三个整数表示 $x_i, y_i, r_i$。

输出格式

输出共 $1$ 行，一个浮点数表示答案（四舍五入保留两位小数）。

样例

输入 #1

4
0 0 1
2 0 2
-3 0 1
4 4 1

2.47

解释 #1

使用魔法回路连接第 $1$、$3$ 个魔法阵，长度为 $1$。

使用魔法回路连接第 $2$、$4$ 个魔法阵，长度为 $2\sqrt{5} - 3 = 1.47$。

总长度 $2.47$。

数据范围

• 对于 $40\%$ 的评测用例，$n \leq 500$。
• 对于 $100\%$ 的评测用例，$1\leq n \leq 5000$，$|x_i|, |y_i| \leq 2000$，$0 < r_i \leq 20$。