F. Waterfall Matrix
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Radewoosh has recently discovered a special type of matrix. We say that a square matrix containing integers is a Waterfall Matrix if the number in each cell is greater than or equal to the numbers directly below and to the right, if they exist. In other words, a Waterfall Matrix $$$M$$$ of size $$$n \times n$$$ is a matrix in which for all pairs $$$(i, j)$$$ satisfying $$$1 \leq i \leq n$$$ and $$$1 \leq j \leq n-1$$$, we have $$$M_{i, j} \geq M_{i, j+1}$$$ and $$$M_{j, i} \geq M_{j+1, i}$$$.

Radewoosh would like to create a Waterfall Matrix of size $$$n \times n$$$. For $$$n$$$ of its cells, he has come up with the values he would like to enter. Unfortunately, it may not be possible to enter exactly the value he wants in each chosen cell. Therefore, he decided to create a matrix that minimizes the sum of the absolute differences between what he wanted to enter and what he actually entered in the respective cells.

Formally, Radewoosh has a list of triplets of numbers $$$(a_i, b_i, c_i)$$$ and wants to choose a Waterfall Matrix $$$M$$$ to minimize the value of $$$\sum_i |M_{a_i, b_i} - c_i|$$$. Help him and output the minimum value that the mentioned sum can achieve if Radewoosh optimally chooses his matrix.

Input

The first line of the standard input contains a single integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$), indicating the size of the matrix Radewoosh wants to draw and the number of fields he has chosen.

In each of the next $$$n$$$ lines, there are three integers $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$ ($$$1 \leq a_i, b_i \leq n; 1 \leq c_i \leq 10^9$$$), as described in the task.

It is guaranteed that for $$$i \neq j$$$, $$$(a_i, b_i) \neq (a_j, b_j)$$$.

Output

The output should contain a single integer as described in the task.

Example
Input
5
1 3 5
3 2 1
3 3 3
4 4 1
3 5 4
Output
3
Note

One of the optimal matrices that Radewoosh can choose looks as follows:

For the above matrix, we can calculate the result as follows:

$$$|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$$$