在虚构的 Manteiv 国中，有 $n$ 座城市，编号从 1 到 $n$。我们可以将这些城市视为位于二维平面坐标系中，其中城市 $i$ 的坐标为 $(x_i, y_i)$。没有两座城市位于同一位置。

共有 $m$ 条高速公路，编号从 1 到 $m$，每一条都是以两座不同城市为端点的线段，且沿线设有若干个景点。具体来说，第 $j$ 条高速公路有 $a_j$ 个景点，连接城市 $u_j$ 和 $v_j$。由于高速公路上的交叉口会导致交通拥堵，且在现有高速公路上方修建另一条高速公路成本高昂，因此保证：

• 任意两条高速公路除了在城市处外，不会在任何其他点相交，
• 没有高速公路会穿过除其两个端点以外的任何城市，且
• 每对城市之间最多只有一条高速公路。

Manteiv 旅游部希望选择一个城市子集作为旅游景点。直观上，旅游部希望所选城市中，有许多对城市之间由拥有大量景点的高速公路相连。形式上，非空城市子集 $S$ 的吸引力得分定义如下：

• 对于每一对整数 $(a, b)$，满足 $a < b$，城市 $a$ 和 $b$ 都在 $S$ 中，且它们之间由一条高速公路相连，将该高速公路上的景点数量加到得分中。
• 令 $f(S)$ 为满足 $a < b$，城市 $a$ 和 $b$ 都在 $S$ 中，且它们之间没有高速公路相连的整数对 $(a, b)$ 的数量。该得分会受到 $10^6$ 乘以 $f(S)$ 的平方的惩罚（负分）。换句话说，从得分中减去 $10^6 \times f(S)^2$。

例如，设 $n = 3$，城市 1 和 2 由一条有 10 个景点的高速公路相连，城市 2 和 3 由一条有 20 个景点的高速公路相连，城市 1 和 3 之间没有高速公路。

• 城市子集 $\{1\}$ 的吸引力得分为 0。
• 城市子集 $\{1, 2\}$ 的吸引力得分为 $10 - 10^6 \times 0^2 = 10$。
• 城市子集 $\{2, 3\}$ 的吸引力得分为 $20 - 10^6 \times 0^2 = 20$。
• 城市子集 $\{1, 2, 3\}$ 的吸引力得分为 $10 + 20 - 10^6 \times 1^2 = -999\,970$。

作为旅游部的顾问，你需要找出所有可能的非空城市子集 $S$ 中的最大吸引力得分。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 100\,000$; $0 \le m \le 300\,000$)。接下来的 $n$ 行，每行包含两个整数。第 $i$ 行包含 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 10^9$)。接下来的 $m$ 行，每行包含三个整数。第 $j$ 行包含 $u_j$、$v_j$ 和 $a_j$ ($1 \le u_j < v_j \le n$; $0 \le a_j \le 10^6$)。保证高速公路满足题目描述中的条件。

输出格式

输出一个整数，表示所有可能的非空城市子集 $S$ 中的最大吸引力得分。

样例

输入 1

3 2
0 0
0 1
1 0
1 2 10
2 3 20

输出 1

20

说明 1

此样例即为题目描述中给出的例子。城市子集 $\{2, 3\}$ 给出了最高吸引力得分 20。

输入 2

3 3
0 0
0 1
1 0
1 2 10
2 3 20
1 3 30

输出 2

60

说明 2

城市和高速公路如图 B.1 所示。通过在 $S$ 中选择城市 1、2 和 3，吸引力得分为 $10 + 20 + 30 - 10^6 \times 0^2 = 60$。

图 B.1：样例输入 #2 的示意图。