Farmer John은 소에게 충분한 물을 주려 우물과 외양간을 잇는 관 $N$개($1 \le N \le 700$)의 지도를 그렸다. 크기가 다른 관이 무질서하게 연결되어 놀랐고 유량을 계산하려 한다.

직렬 관 두 개의 유량은 두 용량의 최솟값이다. 용량 5와 3은 용량 3인 관 하나와 같다.

  +---5---+---3---+    ->    +---3---+

병렬 관의 용량은 합이다.

    +---5---+
 ---+       +---    ->    +---8---+
    +---3---+

다른 곳에 연결되지 않는 관은 제거할 수 있고 전체 용량에 기여하지 않는다.

    +---5---+
 ---+               ->    +---3---+
    +---3---+--

모든 관 미로는 이 규칙으로 하나의 총 용량으로 줄일 수 있다.

지도에서 우물 (A)과 외양간 (Z) 사이 용량을 구하라.

노드 이름이 글자인 예를 보자.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +---3---+---5---+---4---+
                         C       D

BC와 CD를 합친다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

BD와 DZ를 합친다.

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

BZ의 두 갈래를 합친다.

                 B
        A+---3---+---9---+Z

AB와 BZ를 합치면 총 용량 3이다.

        A+---3---+Z

두 끝점으로 표현한 관을 읽고 'A'에서 'Z'까지 순 유량을 구하는 프로그램을 작성하라. 모든 테스트망은 이 규칙으로 줄일 수 있다.

관 $i$는 다른 노드 $a_i$, $b_i$(각 'A-Za-z')를 연결하며 유량 $F_i$($1 \le F_i \le 1,000$)이다. 대소문자 이름은 다르게 취급한다.

처음 50번 제출은 추가 테스트 피드백을 받는다.

입력

• 1번째 줄: 정수 $N$.
• $2,\ldots,N+1$번째 줄: $i+1$번째 줄에 관 $i$의 공백으로 구분한 두 글자와 정수 $a_i$, $b_i$, $F_i$.

출력

• 1번째 줄: 우물 ('A')에서 외양간 ('Z')까지 최대 유량인 정수.

예제

입력 1

5
A B 3
B C 3
C D 5
D Z 4
B Z 6

출력 1

3

문제 작성: Rob Kolstad, 2008