Problem F
Fair brewing

Vats at beer brewery Georgia, USA. Public Domain by Paul Brennan

United Brewery was born through fusions and mergers of various small and local breweries that each produced their own particular kind of beer. The recipes of the smaller breweries were strongly loved by local fan bases, and the beers continued to be brewed at United Brewery. In an effort to prevent unrest between different fan bases, United Brewery adopted a fairness principle: They agreed to brew and distribute an identical amount of each beer.

Naturally, the brewery is interested in brewing the largest total amount of beer possible. Due to limitations of the production facilities at United Brewery, all this turned out to be harder than expected.

United Brewery’s production facilities consist of one tank and one bottling line per beer, as well as some internal joints, connected through a system of pipes. Here is an example with $3$ beers and $4$ joints that corresponds to the first sample input:

Each tank and each bottling line connects to exactly one pipe, but many pipes may connect to the same joint. Each joint can be configured to internally connect disjoint pairs of incident pipes, without further restrictions. For instance, here are $3$ different ways of configuring the same $5$-pipe joint:

A valid configuration of the joints allows beer to flow from the beer tanks to distinct bottling lines. The capacity of each pipe limits the amount of beer that can travel through it. The amount of each beer produced in a valid configuration is the minimum capacity of any pipe through which beer travels in that configuration.

Input

The first line of input consists of $3$ integers: the number $K$ of beer tanks and bottling lines, where $2 \leq K \leq 10$, the number $N$ of joints, where $0 \leq N \leq 1000$, and the number $M$ of pipes, where $K \leq M \leq 10^4$.

The following $M$ lines each consist of three integers $A_ i$, $B_ i$, and $C_ i$ describing the pipes: The $i$th pipe connects $A_ i$ with $B_ i$ and has a capacity $C_ i$. Here, $A_ i$ and $B_ i$ are distinct connection points: Each connection point is a number between $1$ and $2K+N$, where numbers $1, \ldots , K$ represent beer tanks, numbers $K+1, \ldots , 2 K$ represent bottling lines, and numbers $2K+1, \ldots , 2 K + N$ represent joints. There is at most one pipe between each pair of connection points. Moreover, we know that $1 \leq C_ i \leq 10^9$ holds.

Finally, each beer tank and each bottling line connects to exactly one pipe.

Output

If no valid configuration exists, output “Expand brewery”. Otherwise, output a single integer: the amount of each beer produced in the best valid configuration.

3 4 11
1 7 20
2 8 10
3 10 30
4 7 30
5 9 20
6 10 30
7 8 10
8 10 12
8 9 7
7 9 8
9 10 9

9

2 2 5
1 5 2
2 5 2
5 6 2
6 3 2
6 4 2

Expand brewery

2 0 2
1 2 1
3 4 1

Expand brewery