Farmer John muốn đủ nước cho bò nên vẽ $N$ ống ($1 \le N \le 700$) nối giếng với chuồng. Ngạc nhiên trước mạng ống nhiều cỡ nối hỗn loạn, ông muốn tính lưu lượng.

Hai ống nối tiếp cho lưu lượng nhỏ nhất của hai dung lượng. 5 nối 3 tương đương một ống 3:

  +---5---+---3---+    ->    +---3---+

Song song thì cộng dung lượng:

    +---5---+
 ---+       +---    ->    +---8---+
    +---3---+

Ống không nối thêm gì có thể bỏ, không đóng góp tổng dung lượng:

    +---5---+
 ---+               ->    +---3---+
    +---3---+--

Mọi mê cung ống có thể giảm theo các quy tắc này thành một dung lượng tổng.

Từ bản đồ, tìm dung lượng giữa giếng (A) và chuồng (Z).

Ví dụ với tên nút là chữ:

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

Gộp BC và CD:

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

Gộp BD và DZ:

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

Gộp hai nhánh BZ:

                 B
        A+---3---+---9---+Z

Gộp AB và BZ cho dung lượng ròng 3:

        A+---3---+Z

Viết chương trình đọc ống mô tả bằng hai đầu và tính từ 'A' đến 'Z'. Mọi mạng kiểm thử giảm được bằng các quy tắc này.

Ống $i$ nối nút khác nhau $a_i$, $b_i$ (mỗi trong 'A-Za-z') với lưu lượng $F_i$ ($1 \le F_i \le 1,000$). Tên chữ hoa và thường khác nhau.

50 lần nộp đầu có phản hồi kiểm thử bổ sung.

Dữ liệu vào

• Dòng 1: số nguyên $N$.
• Các dòng $2,\ldots,N+1$: dòng $i+1$ mô tả ống $i$ bằng hai chữ và số nguyên cách nhau bởi dấu cách: $a_i$, $b_i$, $F_i$.

Dữ liệu ra

• Dòng 1: số nguyên, lưu lượng tối đa từ giếng ('A') đến chuồng ('Z').

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3

Tác giả: Rob Kolstad, 2008