说明

在前往巴黎参加 SWERC 的旅途中，Morgane 为她参观的每个纪念碑进行了评分。在这个星期的最后一晚，她计划乘坐热气球，拍摄两张 180° 的城市全景照片，从而获得完美的 360° 视野。她希望两张照片的评分大致相当。

因此，她将按以下步骤进行。她选择两个纪念碑，我们将之称为边界纪念碑，并要求热气球飞行员飞到这两个纪念碑之间。从那里，她拍摄两张 180° 的照片：每张照片展示巴黎的一个侧面，两个侧面由两个边界纪念碑界定。每张照片获得一个评分，即该照片中显示的纪念碑（包括两张照片上都会出现的边界纪念碑）的评分之和。最后，如果两张照片的评分分别为 $A$ 和 $B$，Morgane 的目标是最小化 $A$ 和 $B$ 之间的差异（绝对值）。

从热气球上的视野可以看到，所有纪念碑都会出现在其中一张照片中。

你必须帮助 Morgane 选择合适的边界纪念碑。为此，你会得到一份纪念碑列表。对于 Morgane 参观的每个纪念碑，列表中有一行数据，包含该纪念碑位置的笛卡尔坐标以及该纪念碑的评分。你应该给出 Morgane 可能拍摄的所有照片对中，两张照片评分之间的最小可能差异。

重要提示

Morgane 对每个纪念碑的定位非常精确，没有三个纪念碑位于同一条直线上。

输入格式

输入包含若干行，每行由空格分隔的整数组成：

• 第一行包含纪念碑的数量 $N$；
• 接下来的 $N$ 行每行包含三个整数，分别对应每个纪念碑的 $X$ 坐标、$Y$ 坐标和评分 $G$。

输出格式

输出应包含一行，内容为一个整数，表示 Morgane 可能拍摄的照片对中两张照片评分之间的最小差异（绝对值）。

8
0 0 10
1 1 2
2 1 3
3 2 7
2 3 8
5 2 5
1 5 12
4 5 14

2

提示

数据范围

• $2 \leq N \leq 4000$；
• $0 \leq X, Y \leq 1\,000\,000\,000$ 且 $1 \leq G \leq 1\,000\,000\,000$。

翻译由 DeepSeek 完成