Farmer John は牛に十分な水を与えるため、井戸と牛舎を結ぶ $N$ 本の管（$1 \le N \le 700$）を図にしました。様々な太さの管が乱雑に結ばれていて驚き、流量を計算します。

2管直列の流量は容量の小さい方です。容量5と3は容量3の1管に等価です：

  +---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 の2枝を統合できます：

                 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$ の空白区切りの2文字と整数 $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