题目描述

现在是晚餐时间，母牛们正分散在各个牧场中。Farmer John 按响了电铃，母牛们便开始向谷仓走去。你的任务是找出哪只母牛会最先到达谷仓（给定的测试数据中，总会有且仅有一只最快的母牛）。

晚餐前的挤奶时段，每只母牛都待在属于自己的牧场上，部分牧场可能没有母牛。牧场之间由双向道路连接，两个牧场间可能存在多条道路，牧场也可能存在连接自身的道路。至少有一个牧场与谷仓连通，因此所有母牛都能到达谷仓。

母牛始终选择最短路径行进，且行进速度完全相同，可沿道路任意方向移动。

牧场的标记规则如下：

• 小写字母 a-z 标记的牧场中没有母牛；
• 大写字母 A-Y 标记的牧场中有且仅有一只母牛；
• 谷仓的标记为 Z，谷仓中没有母牛。

输入格式

第一行一个整数 $P$（$1 \leq P \leq 10^4$），表示连接牧场与谷仓的道路总数。

接下来 $P$ 行，每行包含两个字母和一个正整数，两两之间用空格分隔，分别表示道路连接的两个牧场的标号，以及该道路的长度（道路长度不超过 $10^3$）。

输出格式

输出一行，包含两个内容，用空格分隔：最先到达谷仓的母牛所在牧场的标号，以及该母牛走过的最短路径长度。

样例 #1

样例输入 #1

5
A d 6
B d 3
C e 9
d Z 8
e Z 3

样例输出 #1

B 11