Tập đoàn viễn thông đa quốc gia UltraCom hiện sở hữu một hệ thống truyền tin gồm \(N\) trung tâm truyền nhận dữ liệu (gọi tắt là trung tâm) nằm rải rác khắp địa cầu (các trung tâm này được đánh số từ \(1\) đến \(N\)) và \(M\) vệ tinh (gọi tắt là vệ tinh) cũng được phân bố đều khắp trên bầu trời quanh địa cầu (các vệ tinh này được đánh số từ \(1\) đến \(M\)).

Mỗi trung tâm \(i\) đều có thể thiết lập kết nối trực tiếp (để khai thác) với mỗi vệ tinh \(j\) với chi phí xác định \(C_{i,j}\) nào đó.

Hai trung tâm được xem là thông băng với nhau nếu chúng cùng được kết nối với một vệ tinh hoặc chúng cùng thông băng với một số trung tâm khác. Toàn hệ thống của UltraCom đương nhiên vốn là thông băng hoàn toàn, tức là bất kỳ hai trung tâm nào cũng đều thông băng với nhau. Một sự cố bí ẩn vừa diễn ra trong thời gian gần đây đã khiến một số kết nối bị hư hỏng hoàn toàn và hệ thống của UltraCom bị rơi vào tình trạng không thông băng hoàn toàn được, đặt ra nhiệm vụ cấp bách cho UltraCom phải khẩn trương khắc phục hậu quả này.

Sau sự cố, bộ phận phụ trách kỹ thuật của UltraCom đã tiến hành khảo sát toàn hệ thống và nhận thấy rằng:

1. Mỗi trung tâm đều vẫn còn đang kết nối bình thường với một số các vệ tinh đồng thời mỗi vệ tinh đều còn đang được kết nối bởi một số trung tâm nào đó.
2. Một số kết nối vừa bị hỏng sẽ không thuộc diện xem xét khắc phục nữa, do chi phí quá lớn.
3. Hoàn toàn có phương án khả thi để khắc phục hệ thống thông băng hoàn toàn. ðể tiết kiệm chi phí tại thời điểm nhạy cảm của nền kinh tế toàn cầu, ban lãnh đạo tập đoàn quyết định sẽ chỉ thiết lập lại một số kết nối đã bị hư hỏng sao cho tổng chi phí khắc phục là nhỏ nhất có thể.

Yêu cầu

• Xác lập phương án cụ thể và tổng chi phí nhỏ nhất để UltraCom khắc phục sự cố.

Dữ liệu vào

• Dòng đầu ghi tuần tự \(2\) số nguyên dương \(N, M\) \((2 \le M, N \le 1000)\)
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo ghi \(M\) số nguyên \(C_{i,1}, ..., C_{i,M}\) \((-1 \le C_{i,j} \le 10000; i = 1, ..., N; j = 1, 2,…, M)\) với ý nghĩa: \(C_{i,j}\) là chi phí để kết nối trung tâm \(i\) với vệ tinh \(j\) cùng sự lưu ý đặc biệt: \(C_{i,j} = 0\) nếu trung tâm \(i\) vẫn đang kết nối bình thường được với vệ tinh \(j\), \(C_{i,j} = -1\) nếu bỏ qua việc tái lập sự kết nối giữa trung tâm \(i\) với vệ tinh \(j\) (do chi phí quá lớn).
• Tất cảc các số nguyên trên cùng dòng đều cách nhau bởi khoảng trống. Dữ liệu luôn đảm bảo tính đúng đắn để có lời giải, tức là luôn có phương án để UltraCom khắc phục sự cố.

Dữ liệu ra:

• Dòng đầu ghi một số nguyên, là tổng chi phí nhỏ nhất tìm được.
• Dòng thứ \(2\) ghi số nguyên dương \(K\), với \(K\) là số kết nối cần khắc phục.
• \(K\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(c, s\) (cách nhau bởi khoảng trống) cho biết cần tái lập kết nối giữa trung tâm c với vệ tinh s. Nếu có nhiều kết quả (phương án), chỉ cần chỉ ra một trong chúng.

Input 1

4 3 
0 -1 5  
0 4 4 
-1 0 -1 
1 2 0

Output 1

3 
2 
4 1 
4 2

Input 2

4 4 
0 -1 5 3 
-1 4 5 -1 
-1 0 -1 0 
6 7 0 -1

Output 2

12 
3 
1 4 
2 2 
1 3

Ràng buộc:

• 60% số test ứng với 60% số điểm của bài ứng với \(N, M \le 200\).
• Giới hạn thời gian cho mỗi test: 01 giây.