최대 유량

농부 존은 소들이 충분한 물을 마실 수 있도록, 우물에서 외양간까지 물을 보내는 배수관들의 지도를 만들었다. 배수관들은 저마다 다른 용량을 가지고 서로 우연히 연결되어 있으며, 존은 이 배수관망을 통해 흐를 수 있는 유량을 계산하고 싶다.

배수관은 다음 규칙에 따라 하나의 배수관으로 줄일 수 있다.

• 직렬 연결: 두 배수관이 한 줄로 이어져 있으면, 두 용량 중 최솟값만큼만 흐른다. 예를 들어 용량 $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-----------+

이제 B와 Z 사이의 두 배수관이 병렬로 합쳐진다.

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

마지막으로 AB와 BZ가 직렬로 합쳐져 용량 $3$인 배수관 하나가 된다.

        A+---3---+Z

배수관들의 목록이 주어질 때, 위 규칙들을 적용하여 우물 $A$에서 외양간 $Z$까지 흐를 수 있는 최대 유량을 구하여라.

각 노드의 이름은 알파벳 한 글자이며, 대문자와 소문자는 서로 다른 노드로 취급한다(예: B와 b는 다른 노드). $i$번째 배수관은 서로 다른 두 노드 $a_i$와 $b_i$를 잇고 용량 $F_i$ ($1 \le F_i \le 1000$)를 가진다. 물은 배수관을 양방향으로 흐를 수 있다. 같은 두 노드를 잇는 배수관이 여러 개 주어질 수도 있다.

첫째 줄에 배수관의 개수 $N$ ($1 \le N \le 700$)이 주어진다. 이어지는 $N$개의 줄에는 각 배수관의 정보가 주어진다. 각 줄에는 배수관이 잇는 두 노드의 이름(알파벳 대문자 또는 소문자)과 그 배수관의 용량이 공백으로 구분되어 주어진다.

첫째 줄에 노드 $A$에서 노드 $Z$까지 흐를 수 있는 최대 유량을 출력한다.