Anna được giao nhiệm vụ thiết kế hệ thống đường dây cho một trang trại điện gió ngoài khơi mới ở Biển Bắc, gồm ~N~ tuabin, được đánh số ~0, 1, \dots, N-1~. Mục tiêu của cô là bảo đảm tất cả các tuabin đều được kết nối với bờ với chi phí thấp nhất có thể.

Anna có một danh sách ~M~ kết nối có thể xây dựng, mỗi kết nối nối hai tuabin gió và có một chi phí cụ thể. Ngoài ra, thành phố gần đó đã đồng ý chi trả chi phí kết nối một đoạn liên tiếp ~[\ell, r]~ gồm các tuabin với bờ. Nghĩa là, mỗi tuabin ~t~ trong đoạn này (~\ell \le t \le r~) được nối trực tiếp với bờ miễn phí. Nếu tất cả các kết nối có thể xây dựng đều được xây dựng, thì từ một tuabin gió bất kỳ có thể đi đến bất kỳ tuabin gió nào khác. Điều đó có nghĩa là ngay khi một trong các tuabin gió được nối với bờ, ta có thể xây dựng các kết nối sao cho điện từ tất cả các tuabin đều có thể được truyền vào bờ. Tất nhiên, có thêm nhiều kết nối với bờ có thể giúp giảm tổng chi phí. Lưu ý rằng các kết nối miễn phí là những kết nối trực tiếp duy nhất với bờ.

Nhiệm vụ của Anna là chọn một tập con các kết nối có thể xây dựng sao cho tổng chi phí của chúng nhỏ nhất, đồng thời bảo đảm mọi tuabin gió đều có đường nối đến bờ (có thể thông qua các tuabin gió khác).

Để có thể đưa ra quyết định có cơ sở, thành phố cung cấp cho Anna ~Q~ phương án có thể lựa chọn cho đoạn ~[\ell, r]~. Thành phố yêu cầu Anna tính chi phí nhỏ nhất cho từng phương án này.

Input

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên ~N~, ~M~ và ~Q~.

~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i~, ~v_i~ và ~c_i~. Dòng thứ ~i~ mô tả một kết nối có thể xây dựng giữa các tuabin gió ~u_i~ và ~v_i~ với chi phí ~c_i~. Các kết nối này là vô hướng và nối hai tuabin khác nhau. Không có hai kết nối nào nối cùng một cặp tuabin. Bảo đảm rằng nếu tất cả các kết nối có thể xây dựng đều được xây dựng thì từ bất kỳ tuabin gió nào cũng có thể đi đến bất kỳ tuabin gió nào khác (trực tiếp hoặc gián tiếp).

~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~\ell_i~ và ~r_i~, mô tả phương án trong đó bờ được nối trực tiếp với các tuabin gió ~\ell_i, \ell_i+1, \dots, r_i~. Lưu ý rằng có thể có ~r_i = \ell_i~ khi bờ được nối trực tiếp với một tuabin gió duy nhất.

Output

In ra ~Q~ dòng, mỗi dòng ứng với một phương án và chứa một số nguyên là chi phí nhỏ nhất để kết nối các tuabin sao cho mọi tuabin đều có thể truyền điện vào bờ.

Scoring

• ~2 \le N \le 100000~.

• ~1 \le M \le 100000~.

• ~1 \le Q \le 200000~.

• ~0 \le u_i,v_i \le N-1~.

• ~u_i \ne v_i~, và có nhiều nhất một kết nối trực tiếp giữa mỗi cặp tuabin gió.

• ~1 \le c_i \le 1000000000~.

• ~0 \le \ell_i \le r_i \le N-1~.

Lời giải của bạn sẽ được kiểm tra trên một số nhóm test, mỗi nhóm có một số điểm nhất định. Mỗi nhóm test chứa một tập hợp các test. Để nhận được điểm của một nhóm test, bạn cần giải đúng tất cả các test trong nhóm đó.

Subtask	Điểm	Ràng buộc
1	~8~	~M=N-1~ và kết nối thứ ~i~ có ~u_i=i~ và ~v_i=i+1~, tức là nếu xây dựng tất cả các kết nối thì chúng tạo thành một đường đi ~0 \leftrightarrow 1 \leftrightarrow 2 \leftrightarrow \dots \leftrightarrow N-1~
2	~11~	~N,M,Q \le 2000~ và ~\sum(r_i-\ell_i+1) \le 2000~
3	~13~	~r_i=\ell_i+1~ với mọi ~i~
4	~17~	~1 \le c_i \le 2~ với mọi ~i~, tức là mỗi kết nối có chi phí bằng ~1~ hoặc ~2~
5	~16~	~\sum(r_i-\ell_i+1) \le 400000~
6	~14~	~\ell_i=0~ với mọi ~i~
7	~21~	Không có giới hạn gì thêm

Sample Input 1

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

Sample Output 1

14
8
2

Sample Input 2

5 4 4
0 1 3
1 2 1
2 3 5
3 4 2
0 4
2 3
2 4
2 2

Sample Output 2

0
6
4
11

Sample Input 3

7 7 4
6 4 3
1 4 5
3 2 4
0 3 2
5 2 3
4 0 1
1 3 1
0 1
2 3
4 5
5 6

Sample Output 3

12
10
10
10

Sample Input 4

7 7 3
2 6 1
1 0 1
0 5 1
1 2 2
3 4 1
5 3 1
5 4 1
5 6
1 3
3 4

Sample Output 4

5
4
6

Sample Input 5

7 7 4
6 4 3
1 4 5
3 2 4
0 3 2
5 2 3
4 0 1
1 3 1
0 3
0 6
0 1
0 4

Sample Output 5

7
0
12
6

Sample Input 6

9 13 4
0 1 1
2 0 3
1 2 4
5 4 4
2 5 6
3 1 7
8 1 4
6 3 9
0 3 5
3 5 3
4 3 2
6 2 4
7 8 5
1 8
4 7
6 7
1 2

Sample Output 6

1
14
22
24

Sample Input 7

6 5 1
0 1 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
1 1

Sample Output 7

5000000000

Notes

Trong ví dụ thứ nhất, ta được cho đồ thị các kết nối có thể xây dựng trong dữ liệu vào mẫu thứ nhất.

Ta được cho ba phương án. Trong phương án đầu tiên, tuabin ~1~ là tuabin duy nhất có kết nối với bờ. Trong trường hợp này, ta cần giữ lại tất cả các kết nối ngoại trừ kết nối giữa tuabin ~0~ và tuabin ~2~, với tổng chi phí là ~2+3+6+3=14~. Trong phương án tiếp theo, các tuabin ~3~ và ~4~ được nối với bờ. Trong trường hợp này, ta giữ lại các kết nối ~(1,0)~, ~(1,2)~ và ~(2,4)~, với chi phí là ~8~. Trong phương án thứ ba, tất cả các tuabin ngoại trừ tuabin ~0~ đều được nối với bờ. Trong trường hợp này, ta chỉ cần nối tuabin này với một tuabin khác, và ta thực hiện điều đó bằng cách chọn kết nối ~(0,1)~.

Ví dụ thứ nhất và thứ sáu thỏa mãn ràng buộc của các nhóm test ~2~, ~5~ và ~7~. Ví dụ thứ hai và thứ bảy thỏa mãn ràng buộc của các nhóm test ~1~, ~2~, ~5~ và ~7~. Ví dụ thứ ba thỏa mãn ràng buộc của các nhóm test ~2~, ~3~, ~5~ và ~7~. Ví dụ thứ tư thỏa mãn ràng buộc của các nhóm test ~2~, ~4~, ~5~ và ~7~. Ví dụ thứ năm thỏa mãn ràng buộc của các nhóm test ~2~, ~5~, ~6~ và ~7~.

Ghi công và giấy phép

Bài toán này có nguồn gốc từ EGOI 2025 (Olympic Tin học nữ châu Âu), Ngày 1, được tổ chức tại Bonn, Đức.

• Đề bài gốc: Wind Turbines

• Tác giả: Yaw Chur Zhe, Tia Shi Wei.

• Chủ sở hữu bản quyền: Olympic Tin học nữ châu Âu 2025.

• Tài liệu chính thức: Đề bài và lời giải · Dữ liệu kiểm thử, trình chấm và các bản dịch

• Giấy phép: Creative Commons Ghi công – Chia sẻ tương tự (CC BY-SA), theo siêu dữ liệu chính thức của bài toán. Siêu dữ liệu không chỉ rõ phiên bản giấy phép.

• Các thay đổi: Dịch sang tiếng Việt và định dạng lại cho ClueOJ.

Bản dịch này được phân phối theo cùng các điều khoản CC BY-SA áp dụng cho bài toán gốc.

ClueOJ không có quan hệ liên kết với EGOI hoặc ban tổ chức EGOI 2025, cũng không được các bên này chứng thực.