{"trustable":false,"sections":[{"title":"Đề","value":{"format":"MD","content":"Một liên minh của các nhà cung cấp Internet châu Âu quản lý một mạng lưới truyền trục chính lớn, với các liên kết trực tiếp giữa một số 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 tải một thông điệp trên một liên kết có chi phí đi kèm. Như thông thường 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 để truyền dữ liệu 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 mạng lưới này, cần liên tục gửi dữ liệu đến tất cả các nút trong mạng lưới. Để giúp giảm thiểu chi phí, cần chọn các liên kết mạng sẽ được sử dụng để truyền dữ liệu. Bộ 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 lưới.\n\nĐể hỗ trợ 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í truyền tải tối thiểu để đến tất cả các thành phố của trục chính.\n\nCho một tập hợp các liên kết mạng, tính toán chi phí truyền tải tối thiểu để đạt được tất cả các nút."}},{"title":"Input","value":{"format":"MD","content":"Dữ liệu đầu vào bao gồm nhiều bài kiểm tra, dòng đầu tiên của đầu vào chứa số lượng bài kiểm tra.\n\nCó một dòng trống trước mỗi tập dữ liệu.\n\nDòng đầu tiên của mỗi tập dữ liệu chứa một số nguyên dương M, không lớn hơn 2,000, là số lượng thành phố có kết nối mạng.\n\nDòng thứ hai chứa một số nguyên N không lớn hơn 50,000, là số lượng liên kết hiện có. \n\nMỗi trong số N dòng tiếp theo chứa biểu diễn của một liên kết. \n\nMỗi dòng chứa hai chuỗi và một số nguyên, được tách ra bằng khoảng trắng, B E C, trong đó B và E là tên thành phố đầu mút 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 tải trên liên kết đó."}},{"title":"Output","value":{"format":"MD","content":"Đối với mỗi bài kiểm tra, đầu ra bao gồm một dòng duy nhất chứa một số nguyên là chi phí truyền tải tối thiểu để gửi dữ liệu đến tất cả thành phố.\n\nIn một dòng trống giữa các tập dữ liệu."}},{"title":"Test","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003einput\u003c/th\u003e\n \u003cth\u003eoutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\n1\n\n4\n5\nlisbon london 6\nlisbon paris 5\nlondon paris 1\nlondon berlin 2\nparis berlin 10\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}