{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Một liên minh các nhà cung cấp Internet ở châu Âu quản lý một mạng backbone lớn, với các liên kết trực tiếp (kết nối) giữa một số lượng lớn các thành phố ở châu Âu. Một liên kết giữa một cặp thành phố là hai chiều. Việc truyền một tin nhắn trong một liên kết có một chi phí liên quan. Như thường thấy trên Internet, có thể sử dụng một chuỗi (không giới hạn) các liên kết trực tiếp để chuyển dữ liệu gián tiếp giữa bất kỳ cặp thành phố nào.\n\nĐể cho phép phát sóng các chương trình TV sử dụng backbone này, cần phải liên tục gửi dữ liệu đến tất cả các nút trong mạng. Để giúp giảm thiểu chi phí, cần phải chọn các liên kết mạng sẽ được sử dụng để truyền dữ liệu. Tập hợp các liên kết được chọn phải được kết nối và bao gồm tất cả các nút trong mạng.\n\nĐể giúp liên minh quản lý mạng của mình, bạn được yêu cầu tạo một chương trình tính toán chi phí tối thiểu để truyền dữ liệu đến tất cả các thành phố của backbone.\n\nCho một tập hợp các liên kết mạng, hãy tính toán chi phí truyền tải tối thiểu để tiếp cận tất cả các nút.\n\n### Đầu vào\nĐầu vào bao gồm nhiều bộ test, dòng đầu tiên của đầu vào chứa số lượng bộ test.\nCó một dòng trống trước mỗi bộ dữ liệu.\nDòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên dương M, không lớn hơn 2,000, với số lượng thành phố có kết nối mạng. Dòng thứ hai chứa một số nguyên N không lớn hơn 50,000, với số lượng liên kết hiện có. Mỗi dòng trong số N dòng tiếp theo chứa biểu diễn của một liên kết. Mỗi dòng chứa hai chuỗi và một số nguyên, cách nhau bởi khoảng trống, B E C, nơi B và E là tên của các thành phố ở hai đầu của liên kết mạng, không quá 8 ký tự, và C là một số nguyên dương, không lớn hơn 30, đại diện cho chi phí truyền trong liên kết.\n\n### Đầu ra\nĐối với mỗi bộ test, đầu ra bao gồm một dòng duy nhất chứa một số nguyên với chi phí truyền tải tối thiểu để gửi dữ liệu đến tất cả các thành phố.\n\nIn một dòng trống giữa các bộ dữ liệu.\n\n### Sample Input\n```\n1\n4\n5\nlisbon london 6\nlisbon paris 5\nlondon paris 1\nlondon berlin 2\nparis berlin 10\n```\n\n### Sample Output\n```\n8\n```"}}]}