목초지에서 우리로 돌아오는 최단 거리 소 (제일 빨리 우리로 돌아오는 소)를 구하는 문제이다.

목초지는 a-z ,A-Y 로 표현되고 , 우리는 대문자 Z 으로 표시한다. 소문자 목초지에는 소들이 없고 대문자 목초지에는 소가 한마리 있다. (물론 우리 Z 에는 소가 없다)

목초지 와 우리는 연결되어 있고 하나 이상의 길을 가진다. 우리에 가장 빨리 도착하는 소는 한 마리뿐이라고 하자.

입력 형식

• Line 1: 정수 P (1 <= P <= 10000)
  목초지(혹은 우리)에 연결된 길의 수
• Line 2..P+1:
  두개의 문자와 정수. 목초지(혹은 우리)의 이름과 그들 사이의 거리(1 <= distance <= 1000)

출력 형식

입출력 예

입력 

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

출력

B 11

hint

출처: usaco