{"code":"23_hsg12_hanoi_tg","name":"Trạm gác trung tâm","description":"*Nguồn: Học sinh Giỏi THPT Hà Nội năm 2022 - 2023*\r\n\r\nBan quản lý rừng nguyên sinh đang quản lý một khu vực rộng lớn. Họ đã xây dựng $N$ trạm canh gác rừng (được đánh số từ $1$ đến $N$) và các trạm này được kết nối với nhau bởi $M$ con đường. Trong $N$ trạm canh gác người ta đã chọn ra $K$ trạm làm trạm gác trung tâm - nơi điều hành các trạm gác nhỏ hơn và chứa các dụng cụ, phương tiện bảo về rừng. Để đi lại và vận chuyển thiết bị dễ dàng giữa các trạm gác trung tâm, Ban quản lý quyết định nâng cấp một số con đường sao cho $K$ trạm gác trung tâm đều đi được đến nhau.\r\n\r\n**Yêu cầu:** Hãy chọn các con đường nối $K$ trạm gác trung tâm để nâng cấp sao cho tổng độ dài các con đường này là nhỏ nhất.\r\n\r\n#### Input\r\n\r\n*Dữ liệu vào từ tệp văn bản `TG.INP`:*\r\n- Dòng đầu tiên ghi ba số nguyên dương $N, M, K$ lần lượt là số lượng các trạm gác, số các con đường nối giữa các trạm gác và số lượng các trạm gác trung tâm $(1 \\le N \\le 500; \\ N-1 \\le M \\lt \\dfrac{N^2}{2}; \\ 1 \\lt K \\le N);$\r\n- Dòng thứ hai ghi $K$ số nguyên là số hiệu của $K$ trạm gác trung tâm$;$\r\n- Trong $M$ dòng tiếp theo, mỗi dòng ghi ba số nguyên $u, v, c$ với ý nghĩa con đường hai chiều nối trực tiếp giữa hai trạm $u$ và $v$ có độ dài là $c$ $(1 \\lt c \\le 10^9).$\r\n\r\n#### Output\r\n\r\n*Kết quả ra tệp văn bản `TG.OUT`:*\r\n- Một dòng duy nhất chứa tổng độ dài các con đường thoả mãn yêu cầu trên.\r\n\r\n#### Example\r\n\r\n???+ question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 8 3\r\n        1 3 5\r\n        1 2 2\r\n        1 3 10\r\n        1 4 12\r\n        2 4 5\r\n        2 5 7\r\n        3 4 2\r\n        3 5 10\r\n        4 5 6\r\n        ```\r\n        \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        15\r\n        ```\r\n\r\n#### Note\r\n\r\n- Cần làm các con đường:\r\n    ```\r\n    1 2\r\n    2 4\r\n    3 4\r\n    4 5\r\n    ```\r\n- Tổng độ dài nhỏ nhất là: $15$.\r\n\r\n#### Constraint\r\n\r\n- Có $40\\%$ số test ứng với $40\\%$ số điểm của bài thoả mãn: $K = N, \\ N \\le 500;$\r\n- $30\\%$ số test tiếp theo ứng với $30\\%$ số điểm của bài thoả mãn: $K \\le 10, \\ N \\le 200;$\r\n- $30\\%$ số test còn lại với $30\\%$ số điểm của bài không có ràng buộc gì thêm.","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}