题目背景

荒野里的哨所彼此离得很远，架线成本随距离增长。好在远方有一座中心塔——愿意付接入费的哨所可以直接"越级"通话，不必和邻居拉线。

题目描述

平面上有 $n$ 座哨所，第 $i$ 座哨所的坐标为 $(x_i,y_i)$。要给哨所建立通信网络，有两种手段：

• 在哨所 $i$ 与哨所 $j$ 之间架设一条线路，成本为它们的曼哈顿距离 $|x_i-x_j|+|y_i-y_j|$；线路是双向的；
• 哨所 $i$ 也可以直接接入远方的中心塔，成本为 $h_i$。所有接入中心塔的哨所可以借助中心塔互相通话。

要求任意两座哨所之间都能互相通话（可以通过若干座哨所中转，也可以都接入中心塔）。求最小的总成本。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行三个整数 $x_i,y_i,h_i$。

输出格式

输出一行一个整数，表示最小总成本。

输入输出样例 #1

输入 #1

4
0 0 3
1 0 5
100 0 3
101 0 5

输出 #1

8

说明

样例解释

$1$ 号与 $3$ 号哨所各付接入费 $3$ 直接连上中心塔（共 $6$），$2$ 号与 $1$ 号之间架线（距离 $1$），$4$ 号与 $3$ 号之间架线（距离 $1$），总成本 $8$。若全部架线，至少需要 $1+99+1=101$；若四座哨所都接中心塔则需要 $16$。

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 3000$，$0\le x_i,y_i\le 10^9$，$1\le h_i\le 10^9$。