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