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