Chọn Vị Trí Trang Trại

Có $N$ thị trấn được kết nối bởi $M$ con đường hai chiều. Trong số đó có $K$ thị trấn có chợ. Một nông dân muốn xây trang trại tại một thị trấn không có chợ. Mỗi ngày, ông xuất phát từ trang trại, ghé thăm tất cả $K$ chợ theo thứ tự tối ưu, rồi trở về trang trại.

Tìm tổng quãng đường nhỏ nhất mà nông dân phải đi mỗi ngày, xét trên tất cả các vị trí trang trại có thể.

Dữ liệu vào

• Dòng 1: Ba số nguyên $N$, $M$, $K$
• $K$ dòng tiếp theo: Chỉ số của thị trấn có chợ
• $M$ dòng tiếp theo: Ba số nguyên $u$, $v$, $w$ — con đường nối $u$ và $v$ với độ dài $w$

Dữ liệu ra

Một số nguyên — quãng đường nhỏ nhất.

Ràng buộc

• $1\le N\le 10000$
• $1\le M\le 50000$
• $1\le K\le 5$
• $1\le w\le 1000$

Ví dụ