解析磁场

矿区深处是一片磁场——不是物理的磁场，是Zero的影响力场。每个节点有一个坐标和权值，节点之间的连线代表影响力传播的路径。Echo说，要找到一个节点，使得所有其他节点到它的影响力之和最小。

"那就是磁场的心脏。"Echo说，"影响力最小的点，就是Zero最脆弱的地方。"

"咋个找？"CC问，"一个个试？"

"节点太多，一个个试太慢。"你说，"先找一个大概的中心——把所有节点的坐标平均一下，得到一个近似的心脏位置。然后在它附近的一小片区域里，逐个精算。"

"这像……"CC想了想，"先用大网捞信号，再在网里挑最大的？"

"对。"

你开始写。先切分——把整个空间切成很多小块，每块里预先算出节点的数量和重心。然后找一个全局近似重心，再在这个重心的周围几小块里逐个精算每个节点的总影响力。

屏幕上跳出了结果。第47号节点——坐标(47, 47)——的总影响力最小。

"又是47。"CC说。

"磁场的心脏。"Echo说，"Zero把最脆弱的点藏在了最显眼的位置。"

"那我们去打它？"

"不。"Echo说，"我们绕着它走——从心脏切入，直取Zero的神经中枢。"

题目描述

$n$ 个点，每个点有权值。求一个点，使得所有其他点到它的带权距离之和最小。

输入格式

$n$。然后 $n$ 行，每行坐标和权值。

输出格式

最小带权距离和对应的点编号。

输入样例

3
0 0 5 1 10
5 0 10 2 15
10 0 3 1 20

输出样例

0

提示

• 分块近似。先找全局重心，再在重心附近的小块内暴力枚举。
• 或直接枚举所有点计算。

磁场的尽头，是一片由数据流构成的森林。树木不是植物，是权限结构的可视化。每棵树有成千上万个节点，节点之间的连线代表权限的传递。Echo说，要找到这棵树里最长的路径——从某个节点出发，沿着连线走，能走到的最远的距离。

"那就是树的直径。"Echo说，"Zero的权限树里，最长的路径代表最深层的控制链。"

"咋个找？"CC问，"一条条试？"

"不。"你说，"先找一个平衡点——让树的左右两边尽量均衡。然后从那个点开始，向两边同时探索。每砍断一根树枝，就把它下面的小树单独处理。"

"这像……"CC想了想，"像砍树。先找到树干最粗的地方，然后一层一层剥下去。"

"对。"