Problem Description

On a two-dimensional plane, there are $ N $ cities. The coordinates of the $ i $th city are $ (x_i, y_i) $. Initially, the amount of water in the $ i $th city is $ a_i $ liters.

Snuke can transport any amount of water from one city to another. However, water leaks a bit while being transported. When transporting $ l $ liters of water from the $ s $th city to the $ t $th city, the amount of water remaining when it reaches the destination is $ max(l - d_{s,t}, 0) $. Here, $ d_{s,t} $ represents the Euclidean distance between the $ s $th city and the $ t $th city. Snuke can repeat this type of operation any number of times.

Snuke wants to maximize the minimum amount of water in the $ N $ cities. Find the maximum $ X $ such that it is possible to distribute at least $ X $ liters of water to every city.

Input Format

The input is given from the standard input in the following format:

$ N $ $ x_1 $ $ y_1 $ $ a_1 $ : $ x_N $ $ y_N $ $ a_N $

Output Format

Output the maximum value of the minimum amount of water in the $ N $ cities. The absolute or relative error must be no more than $ 10^{-9} $.

Sample Input and Output

Sample Input #1

3
0 0 10
2 0 5
0 5 8

Sample Output #1

6.500000000000

Sample Input #2

15
335279264 849598327 822889311
446755913 526239859 548830120
181424399 715477619 342858071
625711486 448565595 480845266
647639160 467825612 449656269
160714711 336869678 545923679
61020590 573085537 816372580
626006012 389312924 135599877
547865075 511429216 605997004
561330066 539239436 921749002
650693494 63219754 786119025
849028504 632532642 655702582
285323416 611583586 211428413
990607689 590857173 393671555
560686330 679513171 501983447

Sample Output #2

434666178.237122833729

Notes/Hints

Constraints

• $1 \leq N \leq 15$
• $0 \leq x_i, y_i, a_i \leq 10^9$
• All values inputted are integers.
• No two cities are in the same location.

Sample Explanation 1

The optimal solution is to transport $ 3.5 $ liters of water from the first city to the second city. After the operation, the amount of water in both the first and second cities will be $ 6.5 $ liters, and the amount of water in the third city will be $ 8 $ liters.

见题面 Input 部分

见题面 Output 部分