题目描述

请注意，题面中并没有说明水管是单向的还是双向的（虽然应该是双向的）。数据保证无论将水管视作单向还是双向得到的结果相同。 农夫约翰总是希望他的奶牛有足够的水，因此他绘制了一张农场上连接水井和谷仓的 $N（1 \leq N \leq 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-z、A-Z$），流量为 $F_i$（$1 \leq F_i \leq 1,000$）。注意，小写和大写的节点名称应视为不同。

形式化题意：求出 $A$ 到 $Z$ 的最大流。

输入格式

第 $1$ 行：一个整数：$N$

第 $2$ 行到第 $N+1$ 行：第 $i+1$ 行描述第 $i$ 根水管，包含两个字母和一个整数，均以空格分隔：$a_i$，$b_i$ 和 $F_i$。

输出格式

第 $1$ 行：一个整数，表示从水井 $A$ 到谷仓 $Z$ 的最大流量。

输入输出样例 #1

输入 #1

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

输出 #1

3