메시라이브

문제

운전 브이로그를 찍어 큰 부와 명예를 얻은 메시는 라이브 방송에 도전하려고 한다.

인덱스국에는 $n$개의 도시가 있다. 메시가 방송을 켜는 도시는 $1$번 도시이고, 편집자가 사는 $n$번 도시로 영상을 전송하려고 한다. 인덱스국의 영토는 무한한 2차원 좌표평면이고, 각 도시는 무시할 수 있는 크기의 한 점으로 볼 수 있다. 메시는 원활한 통신을 위해 두 도시 사이를 잇는 양방향 유선 통신 회선 $m$개를 설치했다. 각 통신선은 두 도시를 양 끝점으로 하는 선분 형태로, 간섭을 방지하기 위해 서로 다른 두 통신선은 끝점 이외에 교차하지 않는다. $i$번 통신선은 최대 $w_{i}$bps로 데이터를 전송할 수 있다. 아래 그림은 가능한 통신 네트워크의 한 예이다.

각 원은 도시, 선분들은 통신선을 의미한다.

한 도시에 통신선을 통해 전달된 데이터는 바로 도시에 연결된 다른 통신선을 타고 흘러나갈 수 있다. 데이터가 통신선을 통해 전달되는 시간은 무시할 수 있을 정도로 짧다. $i$번 통신선을 통해 전달되는 단위 시간 당 데이터의 양은 용량을 넘을 수 없음에 주의하자. 아래 그림은 데이터가 전달되는 모습의 한 예로, $1$번 도시에서 $8$번 도시까지 25bps의 속도로 데이터가 전달되고 있다.

붉게 표시된 통신선은 데이터를 최대한으로 수송하고 있는 선들이다.

메시는 고화질 영상을 전송하기 위해, $1$번 도시에서 $n$번 도시로 최대 몇 bps의 데이터를 전송할 수 있는지 여러분에게 물어보았다. 인플루언서 메시를 도와주어 부를 축적해보도록 하자.

입력

입력의 첫 줄에 정수 $n, m$이 주어진다.

이후 $n$개의 줄에 걸쳐 $i$번 도시의 좌표를 나타내는 정수 $x_{i}, y_{i}$가 주어진다. $(1 \le i \le n)$

이후 $m$개의 줄에 걸쳐 $u_{j}, v_{j}, w_{j}$가 공백으로 구분되어 주어진다. $j$번 통신선은 $u_{j}, v_{j}$번 도시를 연결한다. $(1 \le j \le m)$

출력

첫째 줄에 답을 출력한다.

제한

• $2 \le n \le 100\,000$

• $n - 1 \le m \le 300\,000$

• $-10^{9} \le x_{i}, y_{i} \le 10^{9}$

• 두 도시가 같은 점에 있는 경우는 없다.

• $1 \le u_{i} \neq v_{i} \le n$

• $1 \le w_{i} \le 10^{9}$

• 서로 다른 두 간선은 끝점 이외에 만나지 않는다.

• 도시와 통신선은 연결그래프를 이룬다.

8 12
0 0
1 1
1 0
1 -1
2 1
2 0
2 -1
3 0
1 2 8
1 3 10
1 4 11
2 5 7
3 5 6
3 6 7
3 7 4
4 7 8
5 6 6
5 8 100
6 8 9
7 8 10

25

출처

• 문제를 만든 사람: TAMREF

• 문제를 검수한 사람: jhhope1, jhnah917