El Granjero Juan siempre quiere que sus vacas tengan suficiente agua y por lo tanto ha hecho un mapa de las ~N~ ~(1 \leq N \leq 700)~ tuberías de agua en la granja que conectan el pozo al establo. El se sorprendió de encontrar una mezcla salvaje de diferentes tamaños de tuberías conectadas en una manera aparentemente caótica. El quiere calcular el flujo a través de las tuberías.

Dos tuberías conectadas en una fila permiten que fluya una cantidad de agua igual al mínimo de los valores de los valores de flujo de las dos tuberías. El ejemplo de una tubería con capacidad de flujo 5 conectada a una tubería con capacidad de flujo 3 puede se reducida lógicamente a una sola tubería con capacidad de flujo 3:

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

Similarmente, tuberías en paralelo permiten que pase agua que es la suma de sus capacidades de flujo:

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

Finalmente, una tubería que conecta a nada puede ser removida: no contribuye con ningún flujo a la capacidad final.

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

Todas las tuberías en muchos laberintos de tuberias pueden ser reducidas usando estas ideas a una sola con la capacidad de flujo total.

Dado un mapa de las tuberías, determine la capacidad de flujo entre el pozo (~A~) y el establo (~Z~).

Considere este ejemplo donde los nombres de los nodos están rotulados con letras:

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

Las tuberías ~BC~ y ~CD~ pueden ser combinadas:

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

Luego las tuberías ~BD~ y ~DZ~ pueden ser combinadas:

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

Luego las tuberías de ~BZ~ pueden ser combinadas:

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

Luego ~AB~ y ~BZ~ pueden ser combinadas para dar una capacidad neta de 3:

    A+---3---+Z

Escriba un programa que lea un conjunto de tuberías descritas como dos puntos extremos y que calcule el flujo neto de capacidad de 'A' a 'Z'. Todas las redes en los datos de entrada de prueba pueden ser reducidas usando las reglas dadas.

La tubería i conecta dos nodos diferentes ~a_i~ y ~b_i~ (a_i en el rango '~A-Za-z~'; ~b_i~ en el rango '~A-Za-z~') y tiene un flujo ~F_i~ ~(1 \leq F_i \leq 1,000)~. Tenga en cuenta que las letras en minúscula o en mayúscula deben ser tratadas como distintas.

El sistema le proporcionar?retroalimentación extra para sus primeros 50 envios.

Entrada

• Línea 1: un solo entero ~N~.
• Líneas 2..N+1: La línea i+1 describe la tubería i con dos letras y un entero, todos separados con un espacio: ~a_i, b_i,~ y ~F_i~.

Salida

Un solo entero que es el flujo máximo desde el pozo ('~A~') hasta el establo ('~Z~')

Ejemplo de Entrada

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

Ejemplo de Salida

3