Thành phố có \(N\) khu dân cư liên kết với nhau bằng \(M\) con đường một chiều có độ dài xác định. Ban chỉ huy phòng cháy chữa cháy muốn xây dựng một trạm cứu hỏa tại một trong \(N\) khu dân cư. Để tối ưu thời gian phản ứng, trạm cứu hỏa này cần được đặt tại khu dân cư \(i\) sao cho khoảng cách cứu hộ dài nhất từ \(i\) đến các khu dân cư khác reachable từ \(i\) là nhỏ nhất.

Nếu có nhiều khu dân cư thỏa mãn điều kiện, hãy in ra khu dân cư có chỉ số nhỏ nhất.

Đị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^5\)).

Định dạng đầu ra

• In ra hai số nguyên: chỉ số của khu dân cư được chọn để đặt trạm cứu hỏa và khoảng cách cứu hộ lớn nhất từ đó.

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.