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$ 行用空格分隔的兩字母及整數 $a_i$、$b_i$、$F_i$ 描述管 $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