人活着系列之开会

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

人活着如果是为了事业,从打工的到老板的,个个都在拼搏,奋斗了多年终于有了非凡成就,有了一笔丰富的钱财。反过来说,人若赚取了全世界又有什么益处呢?生不带来,死了你还能带去吗?金钱能买保险,但不能买生命,金钱能买药品,但不能买健康,人生在世,还是虚空呀!

在苍茫的大海上,有很多的小岛,每个人都在自己的小岛上。又到了开会的时候了,鹏哥通过飞信告知了每个人,然后大家就开始往鹏哥所在的主岛走,问谁先到达主岛。有几点注意事项:

  1. 主岛一定除了鹏哥之外没有任何人。

  2. 并非所有的小岛上都有人,有的小岛为空。

  3. 样例保证一定有人会先到达主岛。

  4. 小岛上最多只有一个人。

  5. 每个人往主岛走的速度相同

  6. 每个小岛都有一条或多条路与别的小岛相连,可能和自己有一条路相连

  7. 至少有一个小岛和主岛相连,保证所有的人都可以到达主岛

  8. 为了节约时间,每个人都走最短的路径

  9. 两个岛之间也许不只有一条路相连。

  10. 每个小岛都被标记为字母,大写字母代表这个小岛有人,小写字母代表这个小岛没有人,Z代表鹏哥所在主岛的位置

  11. Aa表示两个不同的牧场,A a 8代表的是A岛到a岛的距离是8 A岛上是有人的,a岛上是没有人的。

Input

第一行 :,代表着大海上一共有N条连接小岛的路,(1<= N<=10000)

接下来N行,每一行有两个字母和一个整数len,代表着两个岛的标记是否存在人,以及这两个岛之间的距离。(1<=len<=1000)

Output

最先到达主岛的那个人所在的岛的字母以及他走过的路径长度。

Sample Input

6
A e 6
e Z 8
B c 3
c d 2
D A 12
d Z 3

Sample Output

B 8 

Hint

 

Source

lwn