题目描述

晚餐铃响了，散布在各个牧场的母牛们开始向谷仓赶去。你的任务是找出哪头母牛会最先到达谷仓（测试数据保证有且仅有一头最快的母牛）。

每个牧场通过道路与一个或多个其他牧场相连（可能包含自身）。有时两个牧场之间可能有多条道路相连。至少有一条道路直接连接某个牧场和谷仓，因此所有母牛最终都能到达谷仓，且每头母牛都走最短路径。母牛可以沿任意方向前进，且所有母牛速度相同。

牧场标记方式如下：大写字母 $\texttt{A} \ldots \texttt{Y}$ 表示有母牛的牧场，小写字母 $\texttt{a} \ldots \texttt{z}$ 表示没有母牛的牧场，谷仓标记为 $\texttt{Z}$（谷仓中没有母牛）。

注意 $\texttt{m}$ 和 $\texttt{M}$ 是不同的牧场。

输入格式

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

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

输出格式

单独一行包含两个项目：最先到达谷仓的母牛所在牧场的标号，以及这头母牛走过的路径长度。

样例

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

B 11