데이터 센터의 GPU 공간을 확보하기 위해 리모델링을 돕고 있습니다. 수년간 데이터 센터는 불필요한 네트워크 케이블로 어수선해졌으며, 여러분은 이 혼란을 정리하고 사용하지 않는 케이블을 최대한 많이 회수해 달라는 요청을 받았습니다.

그림 C.1: 예제 입력 1의 예시. 같은 색상의 서버는 연결된 쌍입니다. 제거할 케이블은 점선으로 표시되어 있습니다.

데이터 센터에는 $N$개의 서버와 한 서버를 다른 서버에 연결하는 $N$개의 네트워크 케이블이 있습니다. 각 케이블은 피트(feet) 단위의 길이를 가집니다. 트래픽은 네트워크 케이블을 통해 양방향으로 흐르며, 데이터 센터는 처음에 연결되어 있습니다. 즉, 모든 서버 쌍 $(u, v)$에 대해 $u$에서 $v$로 가는 네트워크 케이블 경로가 존재합니다(중간 서버를 거칠 수 있음). 데이터 센터의 네트워크 트래픽을 감사한 결과, $K$개의 서버 쌍만이 서로 통신해야 한다는 것을 발견했습니다. (참고: 일부 서버는 어떤 쌍에도 포함되지 않을 수 있으며, 두 개 이상의 쌍에 포함될 수도 있습니다.)

이제 모든 연결된 쌍이 서로 연결된 상태를 유지하면서 데이터 센터에서 가능한 한 많은 총 케이블 길이를 제거해야 합니다. 즉, 각 서버 쌍 $(a, b)$에 대해 여러분이 남겨둔 원래의 네트워크 케이블을 통과하는 $a$에서 $b$로의 경로가 존재해야 합니다.

이 제약 조건을 만족하기 위해 남겨두어야 하는 케이블의 최소 총 길이를 구하십시오.

입력

입력의 첫 번째 줄에는 데이터 센터의 서버 수 $N$ ($3 \le N \le 10^5$)과 발견된 서버 쌍의 수 $K$ ($1 \le K \le 10^5$)가 공백으로 구분되어 주어집니다.

다음 $N$개의 줄은 데이터 센터에 원래 있던 네트워크 케이블을 설명합니다. 각 줄에는 세 개의 정수 $u_i, v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$)와 $w_i$ ($1 \le w_i \le 10^9$)가 공백으로 구분되어 주어지며, 이는 서버 $u_i$와 $v_i$를 연결하는 길이가 $w_i$ 피트인 케이블이 있음을 나타냅니다. 서버 쌍을 연결하는 네트워크 케이블은 최대 하나이며, 서버와 케이블로 구성된 그래프는 연결되어 있습니다.

다음 $K$개의 줄에는 서버 쌍을 설명하는 두 개의 정수 $a_j$와 $b_j$ ($1 \le a_j, b_j \le N, a_j \neq b_j$)가 공백으로 구분되어 주어집니다. 각 쌍은 케이블 제거 작업 후에도 경로를 통해 연결된 상태를 유지해야 합니다. 모든 쌍은 서로 다르며, $(a, b)$와 $(b, a)$는 같은 것으로 간주되어 둘 다 쌍으로 나열되지 않습니다.

출력

모든 $K$개의 서버 쌍이 서로 연결된 상태를 유지하기 위해 남겨두어야 하는 네트워크 케이블의 최소 총 길이(피트 단위)를 하나의 정수로 출력하십시오.

예제

예제 입력 1

8 3
5 3 5
1 7 20
3 8 8
7 5 15
5 2 12
1 6 9
5 1 10
7 4 7
3 4
8 2
1 7

예제 출력 1

57

예제 입력 2

5 1
1 3 3
4 2 4
3 4 2
5 2 2
4 1 6
2 1

예제 출력 2

9