题目描述

市中心有$N$家汉堡店，每两家汉堡店间都有一条双向道路。由于汉堡店间的路太过于复杂，决定只保留其中$N-1$条道路(必须保证每两家汉堡店间都连通)，其它道路都无视掉。 经过一段时间的考虑，准备吃光两家汉堡店（两家汉堡店在新图中必须有边）。 假设吃光了$a,b$两家的汉堡，那么就会得到$A/B$的愉悦度： 其中：$A=P_a+P_b$（$P_i$是第$i$家汉堡店的美味度）； $B=$除了道路($a,b$)外，新图中所有道路的权值之和（道路的权值为两家汉堡店之间的欧几里德距离）。 想知道他最多得到的愉悦度是多少。

输入

第一行一个整数$N$，表示汉堡店的个数。 接下来$n$行，每行包括三个整数$x,y,P$，描述一个汉堡店的信息，其中($x,y$)为该汉堡店的直角坐标，$P$为该汉堡店的美味度。

输出

最大的愉悦度（保留两位小数）。

输入样例

4
1 1 20
1 2 30
200 2 80
200 1 100

输出样例

65.00

提示

【样例说明】 保留$(1,2),(3,4),(2,4)$这$3$条边,并且选择$(2,4)$这条边,则$A=30+100=130，B=1+1=2，A/B=65$，可以证明不存在更大的解。 【数据规模及约定】 对于20%数据，满足$2 ＜ N ≤ 5$； 对于50%数据，满足$2 ＜ N ≤ 50$； 对于100%数据，满足$2 ＜ N ≤ 1000，0 ≤ X,Y ≤ 1000，0 ＜ P ＜ 10000$。

完整数据范围与边界约定

3≤N≤1000，坐标为整数且0≤x,y≤1000，1≤P<10000；任意两店坐标不同。可以任意选择一棵生成树及其中一条选中边，B为其他N-2条边长度之和，故B>0。输出最大比值四舍五入到小数点后2位。保证真实最优值与任意舍入分界(k+0.5)/100的距离至少10^-6。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：3≤N≤1000，坐标为整数且0≤x,y≤1000，1≤P<10000；任意两店坐标不同。可以任意选择一棵生成树及其中一条选中边，B为其他N-2条边长度之和，故B>0。输出最大比值四舍五入到小数点后2位。保证真实最优值与任意舍入分界(k+0.5)/100的距离至少10^-6。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1712。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。