Một sàn giao dịch tài chính gồm \(N\) tài khoản và \(M\) lệnh chuyển tiền trực tiếp một chiều. Việc chuyển khoản có thể tốn phí giao dịch hoặc được hoàn tiền khuyến mãi (nhận giá trị âm). Một số vòng lặp giao dịch tạo ra việc hoàn tiền vô hạn (chu trình âm).

Hãy lập bảng tính khoảng cách ngắn nhất giữa mọi cặp tài khoản. Nếu khoảng cách từ \(i\) tới \(j\) có thể giảm xuống âm vô cực (do đi qua chu trình âm), in ra -INF. Nếu không thể đi từ \(i\) tới \(j\), in ra INF.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 200\), \(0 \le M \le 1000\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\), \(w\) (\(1 \le u, v \le N\), \(-1000 \le w \le 1000\)).

Định dạng đầu ra

• In ra ma trận khoảng cách ngắn nhất giữa mọi cặp kích thước \(N \times N\). Các phần tử hàng \(i\) cột \(j\) cách nhau bởi khoảng trắng.

Ràng buộc

• Subtask 1 (40% số điểm): \(N \le 50\), \(M \le 200\).
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.