Cho mạng lưới giao thông gồm \(N\) thành phố và \(M\) con đường một chiều có độ dài xác định. Tổng giám đốc Tèo muốn xây dựng một trạm trung chuyển trung tâm tại một thành phố \(X\). Để tối ưu hóa hoạt động vận chuyển hai chiều từ khắp nơi đổ về \(X\) và từ \(X\) tỏa đi các thành phố, \(X\) cần được chọn sao cho tổng khoảng cách ngắn nhất đi từ mọi thành phố khác tới \(X\) cộng với khoảng cách từ \(X\) tới mọi thành phố khác là nhỏ nhất.

Nếu có nhiều thành phố thỏa mãn điều kiện, hãy in ra thành phố 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 thành phố \(X\) được chọn và tổng khoảng cách tối thiểu.

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.