P7862 [COCI 2015/2016 #2] DRŽAVA

A distant country has just held an election, and a new prime minister has been elected. Currently, there are no roads in this country, so the prime minister decided to connect the cities with two-way roads to form counties and modernize the country. There are $N$ cities in the country. Each county consists of one or more cities. **Two cities are in the same county if and only if one can travel from one city to the other using the newly built roads**. The cities are represented as points in a 2D coordinate system, and a road between two cities is represented as a line segment connecting the corresponding points. The length of a road equals the length of this segment in kilometers. The country is currently suffering an economic recession, so the prime minister decided that, due to a lack of budget, they will not build roads longer than $D$ kilometers. Also, **the prime minister will be happy if there exists at least one county that has a non-empty sub-county (which may include all cities of that county) such that the total population in the sub-county is divisible by $K$**. For example, if $K=4$ and a county has cities with populations `3`, `5`, and `7`, the prime minister will be happy because the total population of the first two cities is `8`. You need to determine the minimum $D$ to help the prime minister reduce costs so that the prime minister becomes happy.

The first line contains two integers $N, K$. The next $N$ lines each contain three integers $x_i, y_i, k_i$, representing the coordinates of the city and its population.

Output one real number in a single line: the minimum $D$, **rounded to three decimal places**.

**[Sample 1 Explanation]** The prime minister can be happy only when all cities are in the same county, so the minimum $D$ is $1.414$. **[Sample 2 Explanation]** The prime minister can be happy only when the first five cities are in the same county, and in this case $D$ is minimal, so the minimum $D$ is $5.657$. **[Constraints]** For $40\%$ of the testdata, $1 \le N \le 10^3$. For $100\%$ of the testdata, $1 \le N \le 5 \times 10^4$, $1 \le K \le 30$, $0 \le x_i, y_i, k_i \le 10^8$. **[Notes]** **The scoring for this problem follows the original problem, with a full score of 160**. This problem is translated from [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**. Translated by ChatGPT 5