{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"Describe","value":{"format":"HTML","content":"Mannix公主要修缮她的宫殿,她的宫殿很大,于是她决定要建造n个玩具屋,每个玩具屋有zi个玩具。玩具屋可以看作二维平面上的点,两个玩具屋之间的距离定义为它们的欧几里得距离。但是,Mannix公主很懒,她只想建造n-1条道路使得所有的玩具屋连通,然而很快就要到sy的生辰了,她需要节约出一些修路的钱来给sy买礼物。\u003cbr\u003e\n于是,Mannix公主请了黑魔法师Kmlver,Kmlver告诉她可以使用黑魔法免除一条道路的花费,现在Mannix公主想要知道怎样修路才可以使得(黑魔法道路链接的两个玩具屋的玩具数之和/道路花费之和)最大。"}},{"title":"Input","value":{"format":"HTML","content":"第一行,一个T(1≤T≤10),表示样例个数。\u003cbr\u003e\n每一个样例中:\u003cbr\u003e\n第一行,n(2 \u003c n ≤ 1000),表示玩具屋个数。\u003cbr\u003e\n接下去n行,每行,x, y, z(0 ≤ x, y ≤ 1000, 0 \u003c z \u003c 100000)表示该玩具屋在位置(x, y),拥有玩具z个。\u003cbr\u003e\n保证公主不会傻乎乎的在同一个位置建玩具屋。"}},{"title":"Output","value":{"format":"HTML","content":"对于每组样例,输出一行答案,表示最大的“黑魔法道路链接的两个玩具屋的玩具数之和/道路花费之和”,四舍五入保留到小数点后两位。\u003cbr\u003e\n道路的花费指的是所选边的距离之和。其中免费边不需要被加上。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e2\n4\n1 1 20\n1 2 30\n200 2 80\n200 1 100\n3\n1 1 20\n1 2 30\n2 2 40\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e65.00\n70.00\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":""}}]}