[COCI2015-2016#2] DRŽAVA

一个遥远的国家刚刚举行了选举，新首相当选了。目前，这个国家没有一条公路，所以首相决定用双向公路把国内的城市连接起来，组成县，使国家现代化。 这个国家共有 $N$ 个城市，每个县由一个或多个城市组成，**两个城市将位于同一个县，当且仅当使用新建的道路可以从一个城市到达另一个城市**。这些城市在二维坐标系中用点来表示，两个城市之间的道路表示为连接两个城市所在点的线段。这条路的长度等于以公里为单位的线段的长度。 该国目前正遭受经济衰退，因此首相决定，由于缺乏预算，他们将不修建超过 $D$ 公里的道路。此外，**如果至少有一个县存在一个非空子县（可以包括该县的所有城市），使得子县内的居民总数可以被 $K$ 整除，首相就会高兴**。例如，如果 $K=4$，一个县的城市分别有 `3`、`5`、`7` 个居民，首相就会高兴，因为前两个城市的居民总数等于 `8`。 请你确定最小的 $D$ 来帮助首相降低成本，使得首相感到高兴。

第一行包含两个整数 $N,K$。 接下来 $N$ 行，每行三个整数 $x_i,y_i,k_i$，分别表示这个城市的坐标和这个城市的人口。

一行一个实数，表示最小的 $D$，**四舍五入保留三位小数**。

3 3
0 4 4
1 5 1
2 6 1

1.414

6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10

5.657

6 5
20 20 9
0 0 3
0 1 1
10 0 1
10 1 6
12 0 3

2.000

**【样例 1 解释】** 只有当所有城市都在同一个县里首相才能高兴，所以最小的 $D$ 为 $1.414$。 **【样例 2 解释】** 当前五个城市都在同一个县里首相才能高兴，且此时 $D$ 是最小的，所以最小的 $D$ 为 $5.657$。 **【数据范围】** 对于 $40\%$ 的数据，$1\le N\le10^3$； 对于 $100\%$ 的数据，$1\le N\le5\times10^4，1\le K\le30，0\le x_i,y_i,k_i\le10^8$。 **【说明】** **本题数据点得分依原题，满分 160**。 题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T6 DRŽAVA**。