Radewoosh 最近发现了一种特殊的矩阵。我们称一个包含整数的方阵为“瀑布矩阵”（Waterfall Matrix），如果其中每个单元格的数值都大于或等于其正下方和正右方的数值（如果存在的话）。换句话说，一个大小为 $n \times n$ 的瀑布矩阵 $M$ 满足：对于所有满足 $1 \le i \le n$ 和 $1 \le j \le n-1$ 的数对 $(i, j)$，都有 $M_{i,j} \ge M_{i,j+1}$ 且 $M_{j,i} \ge M_{j+1,i}$。

Radewoosh 想要创建一个大小为 $n \times n$ 的瀑布矩阵。对于其中的 $n$ 个单元格，他已经确定了想要填入的数值。遗憾的是，可能无法在每个选定的单元格中填入他想要的精确数值。因此，他决定创建一个矩阵，使得他想要填入的数值与实际填入的数值在对应单元格上的绝对差之和最小。

形式化地，Radewoosh 有一个包含 $n$ 个三元组 $(a_i, b_i, c_i)$ 的列表，他想要选择一个瀑布矩阵 $M$，以最小化 $\sum_{i=1}^n |M_{a_i,b_i} - c_i|$ 的值。请帮助他计算并输出在最优选择下，该绝对差之和的最小值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示 Radewoosh 想要绘制的矩阵大小，以及他所选定的单元格数量。

接下来的 $n$ 行中，每行包含三个整数 $a_i, b_i$ 和 $c_i$ ($1 \le a_i, b_i \le n; 1 \le c_i \le 10^9$)，含义如题所述。

保证对于 $i \neq j$，$(a_i, b_i) \neq (a_j, b_j)$。

输出格式

输出一个整数，表示题目描述中所述的最小值。

样例

样例输入 1

5
1 3 5
3 2 1
3 3 3
4 4 1
3 5 4

样例输出 1

3

说明

Radewoosh 可以选择的最优矩阵之一如下所示：

对于上述矩阵，我们可以计算结果如下： $|M_{1,3}-5|+|M_{3,2}-1|+|M_{3,3}-3|+|M_{4,4}-1|+|M_{3,5}-4| = |5-5|+|3-1|+|3-3|+|1-1|+|3-4| = 0+2+0+0+1 = 3$