Bình muốn thiết kế một bản đồ du lịch giữa \(N\) địa điểm và \(M\) tuyến đường hai chiều nối giữa chúng. Để hành trình được êm ái nhất, du khách đi từ \(i\) tới \(j\) mong muốn độ gập ghềnh của con đường gồ ghề nhất trên toàn hành trình là nhỏ nhất.

Hãy tìm độ gồ ghề tối đa nhỏ nhất trên hành trình giữa mọi cặp địa điểm.

Đị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\), \(1 \le w \le 10^9\)), biểu thị độ gồ ghề của tuyến đường hai chiều giữa \(u\) và \(v\).

Định dạng đầu ra

• In ra ma trận độ gồ ghề tối ưu kích thước \(N \times N\). Phần tử hàng \(i\) cột \(j\) là độ gồ ghề lớn nhất tối thiểu trên hành trình từ \(i\) tới \(j\). Nếu không có lối đi nào kết nối, in ra -1. Phần tử hàng \(i\) cột \(i\) 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.