题目描述

晚餐时间到了，奶牛们分散在不同的牧场。Farmer John 按响电铃后，它们开始沿道路前往谷仓。所有奶牛速度相同，并总是选择最短路线。请判断哪一只奶牛最先到达谷仓。

牧场用 a 到 z 以及 A 到 Y 标记，谷仓标记为 Z。大写字母牧场中各有一只奶牛，小写字母牧场中没有奶牛。道路是双向的，两个牧场之间可能有多条道路，也可能出现连接同一牧场的道路。输入保证至少有一只奶牛能够到达谷仓，并且最快到达的奶牛唯一。注意大小写字母表示不同的牧场。

输入格式

第一行输入道路数 $P$。接下来 $P$ 行，每行输入两个字母和一个正整数，表示这两个牧场之间有一条给定长度的双向道路。

输出格式

输出最快到达谷仓的奶牛所在牧场的大写字母，以及它到谷仓的最短路长度，两项之间用一个空格分隔。

数据范围与约定

$1\le P\le10^4$，道路长度不超过 $10^3$。

可见测试数据

输入数据 1

9
A Z 10
B Z 17
A a 56
A Z 52
A Z 80
B a 37
B a 74
a Z 55
a a 67

输出数据 1

A 10

输入数据 2

11
A Z 11
B Z 18
C Z 25
D Z 32
E Z 39
F Z 46
G Z 53
a c 64
E Z 90
E d 38
a d 31

输出数据 2

A 11

输入数据 3

7
A Z 12
B Z 19
B a 84
a a 67
a b 55
b a 98
a a 96

输出数据 3

A 12