Bài tập huấn luyện: Gặp gỡ

Hiện nay IOICamp có rất nhiều thành viên từ N thành phố. Các thành phố đánh số từ 1 đến N. Tại thành phố thứ i (1 £ i £ N) có T_i thành viên và ta gọi tổng số thành viên ở N thành phố là S. Có tất cả M đoạn đường hai chiều nối các thành phố sao cho giữa hai thành phố có không quá một đoạn đường nối trực tiếp và hệ thống đường luôn liên thông. Đối với mỗi đoạn đường, ta biết được thời gian để đi trên các đoạn đường đó.

Do số thành viên rất đông nên khó có thể tập trung tất cả ở một thành phố, vì vậy Admin dự định lập một kế hoạch gặp gỡ giao lưu tại K thành phố sao cho:

• K thành phố được chọn là khác nhau.
• Tổng số các thành viên đến mỗi thành phố giao lưu đều bằng ^S/_K (K luôn đảm bảo là ước của S).
• Tổng thời gian đi đến nơi tập trung của tất cả các thành viên theo con đường nhanh nhất là ít nhất.

Bạn hãy giúp Admin lập một kế hoạch hoàn hảo nhất cho cuộc giao lưu bằng cách chọn ra K thành phố và chỉ ra một phương án để các thành viên có thể di chuyển đến K thành phố này.

Ngay cả nếu kế hoạch của bạn không phải là phương án tối ưu thì bạn cũng nên đưa cho Admin một lời giải tốt nhất của mình.

Input: MEETING.INP

• Dòng đầu tiên ghi 3 số nguyên dương N, M và K lần lượt là số thành phố, số đoạn đường và số thành phố cần chọn.
• Dòng thứ hai ghi N số tự nhiên T₁, T₂, .., T_N là số thành viên ở các thành phố.
• Trong M dòng cuối cùng, mỗi dòng ghi 3 số nguyên dương X, Y, Z với ý nghĩa có đoạn đường hai chiều nối trực tiếp 2 thành phố X, Y và thời gian để đi đoạn đường này là Z.

Output:            MEETING.OUT

• Dòng đầu tiên K số nguyên dương X₁, X₂, .., X_K là tên K thành phố được chọn.
• Dòng thứ i trong N dòng tiếp theo ghi K số tự nhiên D_i1, D_i2, .., D_iK với ý nghĩa sẽ có D_ij thành viên từ thành phố i đến thành phố X_j (1 ≤ i ≤ N, 1 ≤ j ≤ K).

Giới hạn:

• 1 ≤ N ≤ 10000 ; 1 ≤ M ≤ 30000 ; 1 ≤ K ≤ 100
• 0 ≤ T_i ≤ 1000 (với mọi 1 ≤ i ≤ N)
• 0 < Z ≤ 200 với mọi đoạn đường
• Thời gian: 2 s/test
• Bộ nhớ: 16 MB

Ví dụ:

Ghi chú: Với phương án trên thì tổng thời gian di chuyển của các thành viên là 48