성의 연결성

당신은 왕의 명령을 받은 기술자이다. 왕이 성을 지으라고 했다. 공사는 거의 끝나 간다. 성에는 $n$개의 탑과 $m$개의 벽이 들어가며, 각 벽은 두 탑을 잇는다는 것은 이미 정해져 있다. 탑은 평면 위의 점으로, 벽은 탑을 잇는 선분으로 볼 수 있다. 설계도는 몇 가지 합리적인 가정을 만족한다.

• 벽이 탑 하나를 자기 자신과 연결하지 않는다.
• 어느 두 탑 사이에도 벽이 많아야 하나 있다.
• 서로 다른 벽은 탑이 아닌 곳에서 만나지 않는다.
• 두 탑이 같은 위치에 있지 않는다.
• 벽은 양 끝점이 아닌 다른 탑을 지나지 않는다.

당신의 임무는 벽 몇 개를 골라 그 안에 문을 만드는 것이다. 그 뒤에는 성의 모든 벽 양쪽이 문을 통해 외부에서 접근 가능해야 한다. 지형이 다르기 때문에 벽마다 문을 만드는 데 드는 비용이 다르다. 이 임무를 끝내는 데 필요한 최소 비용은 얼마인가?

첫 줄에 두 수 $n$, $m$이 주어진다. 이는 각각 탑의 개수와 벽의 개수이다 ($1 \leq n, m \leq 10^5$).

다음 $n$개 줄 각각에 두 정수 $x\_i$, $y\_i$가 주어지며, 이는 $i$번째 탑을 점 $(x\_i, y\_i)$에 세운다는 뜻이다. 좌표의 절댓값은 $10^6$을 넘지 않는다.

다음 $m$개 줄 각각에 세 정수 $u\_i$, $v\_i$, $c\_i$가 주어진다 ($1 \leq u\_i, v\_i \leq n$, $1 \leq c\_i \leq 10^6$). 이는 탑 $u\_i$와 $v\_i$ 사이에 벽이 들어가며, 이 벽에 문을 만드는 비용이 $c\_i$라는 뜻이다.

먼저 필요한 문을 모두 만드는 데 드는 최소 비용을 한 수로 출력한다. 다음으로 문의 개수 $k$를 출력한다. 그 뒤에는 계획에 따라 문이 있는 벽으로 연결된 탑 쌍 $k$개를 출력한다.