题目描述

高桥君居住的二维平面城市中有 $N$ 个跳板。第 $i$ 个跳板位于点 $(x_i,y_i)$，该跳板的力量为 $P_i$。

高桥君的跳跃力用非负整数 $S$ 表示，初始时 $S=0$。每进行一次训练，$S$ 增加 $1$。

高桥君能够从第 $i$ 个跳板跳到第 $j$ 个跳板，当且仅当

高桥君希望选择一个合适的跳板作为起点，使得从这个起点出发，可以通过若干次跳跃到达任意一个跳板。

请求出为了实现这个目标，高桥君最少需要进行多少次训练。

输入格式

输入从标准输入读入，格式如下：

N
x_1 y_1 P_1
x_2 y_2 P_2
...
x_N y_N P_N

输出格式

输出一个整数，表示最少训练次数。

输入样例 #1

4
-10 0 1
0 0 5
10 0 1
11 0 1

输出样例 #1

2

如果训练 $2$ 次，即 $S=2$，则可以从第 $2$ 个跳板出发到达全部跳板。例如，可以先从第 $2$ 个跳板跳到第 $3$ 个跳板，再从第 $3$ 个跳板跳到第 $4$ 个跳板。

输入样例 #2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

输出样例 #2

18

输入样例 #3

2
0 0 1
1 0 1

输出样例 #3

1

数据范围与限制

• $2\le N\le 200$；
• $-10^9\le x_i,y_i\le 10^9$；
• $1\le P_i\le 10^9$；
• 对于 $i\ne j$，$(x_i,y_i)\ne(x_j,y_j)$；
• 所有输入均为整数。

原题时间限制为 3 秒、内存限制为 1024 MiB；本站评测受全局上限约束，内存限制设为 512 MiB。