Một thành phố có nhiều khu vực cần được kết nối với nhau thông qua các tuyến đường giao thông. Các tuyến đường này có chi phí xây dựng khác nhau, và mục tiêu của thành phố là xây dựng một mạng lưới giao thông sao cho tất cả các khu vực được kết nối và chi phí tổng thể là thấp nhất.

Tuy nhiên, một số tuyến đường giao thông có thể bị hư hỏng hoặc không thể xây dựng do các yếu tố địa lý. Thành phố muốn xây dựng mạng lưới giao thông sao cho tất cả các khu vực được kết nối với nhau, nhưng chỉ sử dụng các tuyến đường có chi phí xây dựng không vượt quá một mức nhất định.

Công ty giao thông muốn áp dụng thuật toán Kruskal để tìm cây khung nhỏ nhất (MST - Minimum Spanning Tree) để kết nối tất cả các khu vực với chi phí thấp nhất. Tuy nhiên, một ràng buộc bổ sung là các tuyến đường có chi phí lớn hơn một giá trị max_cost sẽ không được xem xét trong việc xây dựng mạng lưới.

Yêu cầu:

1. Đầu vào:

• Dòng đầu tiên chứa hai số nguyên n và m (3 ≤ n ≤ 1000, 1 ≤ m ≤ 10000), trong đó:
  • n là số lượng khu vực của thành phố.
  • m là số lượng tuyến đường giao thông có sẵn để kết nối các khu vực.
• Dòng thứ hai chứa một số nguyên max_cost (1 ≤ max_cost ≤ 100000), là chi phí tối đa cho phép để xây dựng một tuyến đường giao thông mới.
• Tiếp theo là m dòng, mỗi dòng chứa 3 số nguyên u, v, c (1 ≤ u, v ≤ n, 1 ≤ c ≤ 100000), trong đó:
  • u và v là hai khu vực có thể kết nối nhau qua tuyến đường giao thông.
  • c là chi phí để xây dựng tuyến đường giao thông giữa khu vực u và khu vực v.

Lưu ý: Các tuyến đường có chi phí lớn hơn max_cost sẽ không được xem xét trong quá trình xây dựng mạng lưới giao thông.

2. Đầu ra:

• In ra tổng chi phí thấp nhất để xây dựng mạng lưới giao thông sao cho tất cả các khu vực đều được kết nối với nhau và không sử dụng tuyến đường có chi phí vượt quá max_cost.
• Nếu không thể kết nối tất cả các khu vực (do không đủ tuyến đường hợp lệ), in ra "Không thể kết nối tất cả các khu vực".

Giải thích:

• Bạn cần áp dụng thuật toán Kruskal để tìm cây khung nhỏ nhất (MST). Tuy nhiên, chỉ các tuyến đường có chi phí nhỏ hơn hoặc bằng max_cost mới được xem xét trong quá trình tìm kiếm cây khung nhỏ nhất.
• Nếu sau khi chạy thuật toán Kruskal, số lượng cạnh trong cây khung nhỏ nhất là ít hơn n-1, điều đó có nghĩa là không thể kết nối tất cả các khu vực, và kết quả sẽ là "Không thể kết nối tất cả các khu vực".

Ví dụ:

Input:

5 7
7
1 2 5
1 3 10
1 4 3
2 3 2
2 4 9
3 4 6
3 5 7

Output:

18

Giải thích:

• Có 5 khu vực và 7 tuyến đường có sẵn. Tuy nhiên, chỉ những tuyến đường có chi phí nhỏ hơn hoặc bằng 7 mới được xem xét.
  • Kết nối khu vực 1 với khu vực 4 (chi phí = 3).
  • Kết nối khu vực 1 với khu vực 2 (chi phí = 5).
  • Kết nối khu vực 2 với khu vực 3 (chi phí = 2).
  • Kết nối khu vực 3 với khu vực 5 (chi phí = 7).

Tổng chi phí là 3 + 5 + 2 + 7 = 18.