Attraction Score

There are $n$ cities, numbered from $1$ to $n$, in the fictional country of Manteiv. The cities lie on a flat plane, and city $i$ is at coordinates $(x_i, y_i)$. No two cities share a position.

There are $m$ highways, numbered from $1$ to $m$. Each highway is a line segment joining two different cities $u_j$ and $v_j$, and it has $a_j$ attraction points. Highways never cross except at cities, no highway passes through a city other than its endpoints, and at most one highway connects any pair of cities.

The Manteiv Ministry of Tourism wants to choose a subset of cities as tourist attractions. The ministry wants many pairs of chosen cities joined by a highway with many attraction points. The attraction score of a non-empty subset of cities $S$ is defined as follows.

For every pair $(a, b)$ with $a < b$ such that cities $a$ and $b$ are both in $S$ and connected by a highway, add the number of attraction points on that highway to the score. Let $f(S)$ be the number of pairs $(a, b)$ with $a < b$ such that cities $a$ and $b$ are both in $S$ but not connected by a highway. Subtract $10^6 \times f(S)^2$ from the score.

For example, let $n = 3$, cities $1$ and $2$ be connected by a highway with $10$ attraction points, cities $2$ and $3$ be connected by a highway with $20$ attraction points, and cities $1$ and $3$ not be connected. The attraction score of $\{1\}$ is $0$. The score of $\{1, 2\}$ is $10 - 10^6 \times 0^2 = 10$. The score of $\{2, 3\}$ is $20$. The score of $\{1, 2, 3\}$ is $10 + 20 - 10^6 \times 1^2 = -999970$.

Find the maximum attraction score among all non-empty subsets of cities $S$.

The first line contains two integers $n$ and $m$ ($1 \le n \le 100000$, $0 \le m \le 300000$). Each of the next $n$ lines contains $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^9$). Each of the next $m$ lines contains $u_j$, $v_j$, and $a_j$ ($1 \le u_j < v_j \le n$, $0 \le a_j \le 10^6$). The highways satisfy the conditions stated in the problem.

Output one integer, the maximum attraction score among all non-empty subsets of cities.