G. Airplane - Quantum Field Theory Edition
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Bessie wants to fly an airplane to escape from Farmer Nhoj's barn to Farmer John's barn! Unfortunately for Bessie, Farmer John and Farmer Nhoj are enemies, so there are no flight paths between Farmer John's barns and Farmer Nhoj's barns.

Here, the earth is a (flat) 2-d infinite Cartesian grid. There are $$$2n$$$ barns, denoted $$$1, 2, \dots, 2n$$$, each of which is located at $$$(x_i, y_i)$$$. Farmer John owns the first $$$n$$$ barns, and Farmer Nhoj owns the next $$$n$$$ barns. Also, there are $$$m$$$ bidirectional flight paths, each of which connects cities $$$u_i$$$ and $$$v_i$$$, and costs $$$e_i$$$ energy to fly through. Each farmer ensures that their barns are connected by flight paths, but since the two farmers are enemies, it is guaranteed that there are no flights between Farmer John's barns and Farmer Nhoj's barns.

Bessie wants to fly from Farmer Nhoj's barn $$$2n$$$ to Farmer John's barn $$$1$$$. Since it is not possible for Bessie to get there, Bessie must quantum tunnel once between two cities, which takes energy given by the Manhattan metric, $$$d((x_1,y_1), (x_2,y_2)) = |x_1-x_2|+|y_1-y_2|$$$.

What is the minimum energy needed for Bessie to fly from barn $$$2n$$$ to barn $$$1$$$?

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n \le 10^5$$$, $$$2(n-1)\le m\le 3\cdot 10^5$$$).

The following $$$2n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$, denoting the x and y coordinates of each of the barns ($$$1 \le x_i, y_i \le 10^9$$$). It is guaranteed that no two airports are in the same location.

Each of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, $$$e_i$$$, denoting a flight path from $$$u_i$$$ to $$$v_i$$$, which takes energy $$$e_i$$$ ($$$1 \le e_i \le 10^9$$$).

It is guaranteed that $$$u_i \ne v_i$$$ and also that each unordered pair $$$(u, v)$$$ is present only once (that is, there are no multiple edges).

All flight paths are bidirectional. It is guaranteed that $$$u_i \le n$$$ if and only if $$$v_i \le n$$$. It is also guaranteed that the barns $$$1, 2, \dots, n$$$ are connected, and that the barns $$$n+1, n+2, \dots, 2n$$$ are also connected.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-3$$$ satisfy $$$1\le n \le 2000$$$, $$$2(n-1)\le m\le 5000$$$.

Tests $$$4-20$$$ satisfy no additional constraints.

Output

Output a single number, the minimum energy for Bessie to fly from barn $$$2n$$$ to barn $$$1$$$.

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

In the sample test case, it is optimal for Bessie to quantum tunnel directly from node 1 to node 6, with cost $$$|2-1| + |1-2| = 2$$$.

—

Problem Idea: jay_jayjay

Problem Preparation: jay_jayjay

Occurrences: Advanced G