Bản đồ mạng lưới giao thông gồm \(N\) nhà kho và \(M\) cây cầu hai chiều. Mỗi cây cầu có một giới hạn tải trọng xe tối đa \(w\) có thể đi qua. Xe đi từ nhà kho \(i\) tới \(j\) theo một tuyến đường sẽ có tải trọng tối đa bị giới hạn bởi tải trọng của cây cầu yếu nhất (cây cầu có tải trọng nhỏ nhất) trên tuyến đường đó.

Hãy tìm tải trọng xe lớn nhất có thể di chuyển giữa mọi cặp nhà kho.

Đị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ị cây cầu hai chiều nối giữa \(u\) và \(v\) chịu được tải trọng tối đa \(w\).

Định dạng đầu ra

• In ra ma trận tải trọng tối đa giữa mọi cặp nhà kho kích thước \(N \times N\). Nếu không có đường đi giữa \(i\) và \(j\), in ra -1. Tải trọng giữa một nhà kho 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.