Problem1413--士兵排阵Ⅲ

1413: 士兵排阵Ⅲ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 77  Solved: 24
[Submit] [Status] [Web Board] [Creator:]

Description

在一个划分成网格的操场上, n个士兵散乱地站在网格点上。 网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、 下、 左、 右移动一步,但是每个士兵有一个疲劳值wi,其移动一步需要耗费wi点体力。假设操场无限大,按照军官的命令,所有士兵都要在某个网格点集合。请计算使所有士兵集合需要的最少体力值之和。

Input

第一行一个正整数n,n<=10^5。
接下来n行,每行三个数x,y,w,其中:-10^5<=x,y<=10^5,1<=w<=100。

Output

输出所有士兵集合需要的最少体力值之和。

Sample Input

1
0 0 1

Sample Output

0

Source/Category