Series‐Parallel Water Flow

Farmer John has mapped out the water pipes connecting the well (node A) to the barn (node Z). The pipes are arranged in a series‐parallel configuration and can be reduced using the following rules:

• Series: Two pipes in series (i.e. connected through an intermediate node) have an effective flow equal to the minimum of their individual flows. That is, for two pipes with flows \(F_1\) and \(F_2\), the series connection has flow \(\min(F_1, F_2)\).
• Parallel: Two pipes in parallel (i.e. connecting the same pair of nodes) have an effective flow equal to the sum of their flows: \(F_1 + F_2\).
• Dead End Removal: A pipe that does not contribute to any connection between A and Z (i.e. a branch terminating in a node other than A or Z) can be removed.

Using these rules, all piping networks provided in the test data can be reduced to a single pipe between A and Z. Your task is to compute the net flow capacity of that pipe.

Note: All pipes are undirected and are described by two endpoints (each a letter in the range A–Z or a–z, where case matters) and a flow capacity \(F_i\) (with \(1 \le F_i \le 1000\)).

The input begins with an integer \(N\) (\(1 \le N \le 700\)), indicating the number of pipes, followed by \(N\) lines in the format:

where a_i and b_i are the endpoints and F_i is the flow capacity. Compute the net flow between A (the well) and Z (the barn) by performing the series, parallel, and dead‐end reductions.

inputFormat

The first line of input contains an integer \(N\) (\(1 \le N \le 700\)), the number of pipes. Each of the following \(N\) lines contains two endpoints and an integer \(F_i\) (\(1 \le F_i \le 1000\)). Endpoints are characters from the ranges A–Z and a–z (with case sensitivity).

Example:

6
A B 3
B Z 6
B C 3
C D 5
D Z 4
X Y 10

Note: In the above, the pipe connecting X and Y is a dead end and does not affect the net flow between A and Z.

outputFormat

Output a single integer representing the net flow capacity between node A and node Z after the full reduction.

For the sample above, the output should be: 3.

sample

6
A B 3
B Z 6
B C 3
C D 5
D Z 4
X Y 10

3