Xây dựng hệ thống đường vượt lũ

Để giảm bớt thiệt hại cho người dân vùng lũ Miền Trung, một công ty tư nhân đã tiến hành xây dựng xong các nhà tránh lũ tại ~N~ địa điểm có địa hình cao ráo. Các địa điểm được đánh thứ tự từ ~1~ đến ~N~. Để thuận tiện cho việc đi lại trong mùa mưa lũ, Lãnh đạo công ty đã lập dự án xây dựng các tuyến đường vượt lũ giữa ~N~ địa điểm trên. Dự án đã tiến hành khảo sát kinh phí để xây dựng mỗi tuyến đường vượt lũ nối giữa địa điểm ~i~ và địa điểm ~j~. Có ~M~ tuyến đường đã được khảo sát và khi xây dựng xong thì người dân có thể đi lại được giữa ~N~ địa điểm trên trong mùa mưa lũ. Do kinh phí xây dựng còn thiếu nên đến nay dự án chỉ xây dựng xong ~K~ tuyến đường trong tổng số ~M~ tuyến đường đã khảo sát. Với yêu cầu cấp bách trong mùa mưa lũ năm nay, Lãnh đạo công ty yêu cầu cần xây dựng thêm một số tuyến đường sao cho người dân có thể đi lại được giữa ~N~ địa điểm trên và kinh phí xây dựng là ít nhất.

Yêu cầu: Hãy tìm một phương án xây dựng thêm các tuyến đường thỏa mãn yêu cầu của Lãnh đạo công ty.

Dữ liệu vào: Cho trong file văn bản XAYDUNG.INP có cấu trúc:

• Dòng 1: Ghi số 3 nguyên dương ~N~ ~M~ ~K~, trong đó ~N~ là số địa điểm, ~M~ là số tuyến đường đã được khảo sát, ~K~ là số tuyến đường đã xây dựng xong, ~(2 ≤ N ≤ 100; N-1 ≤ M ≤ ; 0≤K ≤ M)~.
• ~M~ dòng tiếp theo: Mỗi dòng ghi ~3~ số nguyên dương ~i~ ~j~ ~t~, trong đó ~t~ là kinh phí xây dựng tuyến đường nối giữa địa điểm ~i~ và địa điểm ~j~. Các số được ghi cách nhau ít nhất một dấu cách ~(1 ≤ t ≤ 32767; 1 ≤ i, j ≤ N; i ≠ j)~.
• Dòng ~M + 2~: Ghi ~K~ số, mỗi số là chỉ số của các tuyến đường đã xây dựng xong trong M tuyến đường đã được khảo sát. Các số được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra: Ghi ra file văn bản XAYDUNG.OUT theo cấu trúc:

• Dòng 1: Ghi số ~0~ nếu không xây dựng thêm tuyến đường nào cả. Ngược lại, ghi hai số nguyên dương ~L~ ~S~, trong đó ~L~ là số tuyến đường cần xây dựng thêm, ~S~ là tổng kinh phí xây dựng ~L~ tuyến đường theo phương án tìm được.
• ~L~ dòng tiếp theo: Mỗi dòng ghi ba số nguyên ~i~ ~j~ ~t~, trong đó ~t~ là kinh phí xây dựng tuyến đường nối địa điểm ~i~ và địa điểm ~j~. Các số ghi cách nhau ít nhất một dấu cách.

Ví dụ:

XAYDUNG.INP

4  6  1
1  2  6
1  3  4
1  4  11
2  3  9
2  4  10
3  4  3
5

XAYDUNG.OUT

2  7
3  4  3
1  3  4