Một doanh nghiệp có \(N\) văn phòng liên kết bởi \(M\) tuyến cáp hai chiều với độ trễ truyền tin khác nhau. Hãy lập bảng tính độ trễ ngắn nhất giữa mọi cặp văn phòng để tối ưu hóa việc định tuyến.

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

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 300\), \(0 \le M \le 5000\)).
• \(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\), \(0 \le w \le 10^5\)), biểu thị tuyến cáp giữa \(u\) và \(v\) có độ trễ \(w\).

Định dạng đầu ra

• In ra ma trận độ trễ ngắn nhất kích thước \(N \times N\). Phần tử hàng \(i\) cột \(j\) là độ trễ nhỏ nhất từ văn phòng \(i\) tới \(j\). Nếu không có kết nối, in ra -1. Khoảng cách từ \(i\) tới chính nó in ra \(0\).

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.