Bạn đang hỗ trợ cải tạo một trung tâm dữ liệu để có thêm không gian cho các GPU. Qua nhiều năm, trung tâm dữ liệu đã trở nên bừa bộn với các dây cáp mạng thừa thãi, và bạn được yêu cầu dọn dẹp đống lộn xộn này và thu hồi càng nhiều dây cáp không sử dụng càng tốt.

Hình C.1: Minh họa cho Ví dụ 1. Các máy chủ trong cùng một cặp kết nối có cùng màu. Các dây cáp cần loại bỏ được biểu thị bằng đường nét đứt.

Trung tâm dữ liệu có $N$ máy chủ và $N$ dây cáp mạng liên kết các máy chủ với nhau. Mỗi dây cáp có một độ dài tính bằng feet. Lưu lượng truy cập truyền qua các dây cáp mạng theo cả hai hướng và trung tâm dữ liệu ban đầu được kết nối: với mọi cặp máy chủ $(u, v)$ đều tồn tại một đường đi gồm các dây cáp mạng từ $u$ đến $v$ (có thể đi qua các máy chủ trung gian). Bạn đã kiểm tra lưu lượng mạng của trung tâm dữ liệu và phát hiện ra rằng chỉ có $K$ cặp máy chủ cần liên lạc với nhau. (Lưu ý rằng một số máy chủ có thể không thuộc bất kỳ cặp kết nối nào, hoặc có thể thuộc hai hay nhiều cặp kết nối.)

Bây giờ bạn cần loại bỏ tổng độ dài dây cáp lớn nhất có thể khỏi trung tâm dữ liệu trong khi vẫn giữ cho tất cả các cặp kết nối được liên kết với nhau: với mỗi cặp máy chủ $(a, b)$ như vậy, phải tồn tại một đường đi từ $a$ đến $b$ đi qua các dây cáp mạng ban đầu mà bạn đã giữ lại.

Hãy tìm tổng độ dài tối thiểu của dây cáp phải giữ lại để thỏa mãn điều kiện này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên cách nhau bởi dấu cách $N$ ($3 \le N \le 10^5$) và $K$ ($1 \le K \le 10^5$), số lượng máy chủ trong trung tâm dữ liệu và số lượng cặp máy chủ cần kết nối mà bạn đã phát hiện.

$N$ dòng tiếp theo mô tả các dây cáp mạng ban đầu trong trung tâm dữ liệu. Mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách $u_i, v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$) và $w_i$ ($1 \le w_i \le 10^9$), chỉ ra rằng một dây cáp kết nối máy chủ $u_i$ với máy chủ $v_i$ và có độ dài $w_i$ feet. Có tối đa một dây cáp mạng kết nối một cặp máy chủ và đồ thị các máy chủ và dây cáp là đồ thị liên thông.

Mỗi dòng trong số $K$ dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách $a_j$ và $b_j$ ($1 \le a_j, b_j \le N, a_j \neq b_j$) và mô tả một cặp máy chủ cần kết nối. Mỗi cặp kết nối phải duy trì sự liên kết thông qua một đường đi sau khi bạn đã loại bỏ xong dây cáp. Tất cả các cặp kết nối là riêng biệt; $(a, b)$ và $(b, a)$ được coi là giống nhau và sẽ không cùng xuất hiện trong danh sách các cặp kết nối.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng độ dài tối thiểu của dây cáp mạng (tính bằng feet) phải giữ lại để tất cả $K$ cặp máy chủ vẫn được kết nối với nhau.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

57

Dữ liệu vào 2

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

Dữ liệu ra 2

9