THỰC HÀNH

Trong vườn trẻ, có các nhóm trẻ đang chơi ở những sân chơi khác nhau cùng với cô giáo hướng dẫn (mỗi sân chơi chỉ cho 1 nhóm, mỗi nhóm chỉ có 1 cô giáo hướng dẫn). Mỗi sân chơi có lối đi nối 1 hay nhiều sân chơi khác. Một hay nhiều sân chơi có lối đi nối với sân chơi chính. Một số sân chơi không có học sinh. Có tổng cộng p lối đi.

Có đúng 26 sân chơi được đặt tên từ 'a' đến 'z', sân chơi chính tên là 'z' và theo qui định chung không có nhóm trẻ nào được chơi ở đó. Trên bảng theo dõi ở sân chơi chính, sân nào hiện đang có 1 nhóm trẻ đang chơi được gán tên là chữ in hoa (ví dụ, sân chơi có tên là 'y' hiện đang có 1 nhóm trẻ đang chơi thì trên bảng theo dõi sẽ được gán tên là 'Y')

Khi có thông báo đến giờ nghỉ của vườn trẻ, các nhóm trẻ sẽ theo cô giáo hướng dẫn của mình đi nhanh về sân chính bằng các lối đi rồi mới được bố mẹ đón về - các cô giáo luôn tìm ra con đường ngắn nhất để dẫn các cháu đi (tất nhiên, đường đi mà các cô giáo chọn có thể đi ngang qua một số sân chơi khác). Giả sử tốc độ đi của các nhóm là như nhau và các lối đi đủ rộng để không có nhóm nào phải tạm dừng lại (tránh nhau) khi đi - Người ta cần biết sau khi phát thông báo thì nhóm trẻ hiện đang chơi ở sân chơi nào về tới sân chính trước nhất. Hãy viết chương trình giải quyết yêu cầu trên.

Dữ liệu:

• Dòng đầu tiên chỉ một số nguyên dương là giá trị số p (p ≤ 10000)
• Từ dòng thứ 2 đến dòng thứ p+1 mỗi dòng mô tả một lối đi gồm tên của hai sân chơi và độ dài của lối đi nối chúng, ba nội dung trên một dòng được viết cách nhau ít nhất một dấu cách (độ dài mỗi lối đi không vượt quá 1000)

Kết quả: Ghi ra một dòng duy nhất gồm:

• Một ký tự in hoa là tên của sân chơi có nhóm trẻ về tới sân chính sớm nhất
• Tiếp theo là dấu cách và ghi độ dài đường đi ngắn nhất của nhóm trẻ đó.

Ví dụ:

Input:
6
A d 6
B d 3
C e 9
d z 8
e z 3
B d 1
Output:
B 9