Farmer John sắp chuyển đi! Ông đang cố tìm nơi tốt nhất để xây một trang trại mới nhằm giảm thiểu quãng đường phải di chuyển mỗi ngày.

Khu vực FJ dự định chuyển đến có \(N\) thị trấn (\(1 \le N \le 10\,000\)). Có \(M\) con đường hai chiều (\(1 \le M \le 50\,000\)) nối một số cặp thị trấn. Từ mọi thị trấn đều có thể đến mọi thị trấn khác qua một số con đường. FJ cần bạn giúp chọn thị trấn tốt nhất làm nơi đặt trang trại mới.

Có chợ tại \(K\) thị trấn (\(1 \le K \le 5\)) mà FJ muốn ghé thăm hằng ngày. Cụ thể, mỗi ngày ông dự định rời trang trại mới, ghé thăm \(K\) thị trấn có chợ, rồi quay về trang trại. FJ có thể ghé các chợ theo bất kỳ thứ tự nào mình muốn. Khi chọn thị trấn để xây trang trại mới, FJ chỉ muốn chọn trong \(N-K\) thị trấn không có chợ, vì giá nhà ở những thị trấn này thấp hơn.

Hãy giúp FJ tính quãng đường nhỏ nhất ông phải đi trong lịch trình hằng ngày, nếu ông xây trang trại ở vị trí tối ưu và lựa chọn lịch trình ghé các chợ một cách khôn ngoan nhất có thể.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N\), \(M\), \(K\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+K\): dòng \(i+1\) chứa một số nguyên trong đoạn \(1 \ldots N\), xác định thị trấn có chợ thứ \(i\). Mỗi chợ nằm ở một thị trấn khác nhau.
• Các dòng từ \(2+K\) đến \(1+K+M\): mỗi dòng chứa 3 số nguyên \(i\), \(j\) (\(1 \le i,j \le N\)) và \(L\) (\(1 \le L \le 1000\)), cách nhau bởi dấu cách, cho biết có một con đường dài \(L\) từ thị trấn \(i\) đến thị trấn \(j\).

Dữ liệu ra

In quãng đường nhỏ nhất FJ cần đi trong lịch trình hằng ngày nếu ông xây trang trại ở vị trí tối ưu.

Ví dụ

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

12

Nguồn

USACO 2012 February Contest, Silver - Relocation: https://usaco.org/index.php?page=viewproblem2&cpid=117

Tác giả: Brian Dean, 2012.