يريد 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$ الأنبوب $i$ بحرفين وعدد صحيح مفصولة بمسافات: $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