Problem F
Fair brygning

Ølkar i Georgia, USA. Public Domain by Paul Brennan

Det Forenede Bryggeri blev dannet gennem fusioner og sammenlægninger af forskellige mindre og lokale bryggerier, der hver især bryggede deres egen variant af øl. De små bryggeriers øl var stærkt elsket af lokale fanskarer, og øllene skulle derfor fortsat brygges af det Forenede Bryggeri. For at komme uro mellem de forskellige fanskarer i forkøbet, vedtog det Forenede Bryggeri et retfærdighedsprincip: De blev enige om at brygge og distribuere den samme mængde af hvert øl.

Naturligvis er bryggeriet samtidigt interesseret i at brygge den størst mulige totale mængde øl. Dette er dog blevet sværere end forventet på grund af begrænsninger i det Forenede Bryggeris bryggeudstyr.

Det Forenede Bryggeris bryggeudstyr består af ét ølkar og én tappelinje per ølvariant, samt nogle interne samlinger, der er forbundet gennem et system af rør. Her er et eksempel med $3$ øl og $4$ samlinger, som svarer til den første eksempelindlæsning.

Hvert kar og hver tappelinje er forbundet til præcis ét rør, men flere rør kan forbinde til den samme samling. Hver samling kan indstilles til internt at forbinde disjunkte par af indgående rør, uden yderligere begrænsninger. For eksempel er der her vist $3$ forskellige måder at indstille en $5$-rørs samling:

En gyldig konfiguration af samlingerne lader øllet strømme fra ølkarrene til særskilte tappelinjer. Et rørs kapacitet begrænser mængden af øl, der kan strømme gennem det. Mængden af hver øl, der bliver produceret i en gyldig konfiguration, er den mindste kapacitet for et rør, som øl strømmer gennem, i den konfiguration.

Input

På første linje står 3 heltal: antallet $K$ af ølkar og tappelinjer, hvor $2 \leq K \leq 10$, antallet $N$ af samlinger, hvor $0 \leq N \leq 1000$, og antallet $M$ af rør, hvor $K \leq M \leq 10^4$.

De følgende $M$ linjer består hver af $3$ heltal $A_ i$, $B_ i$, og $C_ i$, der beskriver rørene: Det $i$te rør forbinder $A_ i$ med $B_ i$ og har en kapacitet på $C_ i$. Her er $A_ i$ og $B_ i$ forskellige forbindelsespunkter: Hvert forbindelsespunkt er et tal mellem $1$ og $2K+N$, hvor tallene $1, \ldots , K$ svarer til ølkar, tallene $K+1, \ldots , 2 K$ svarer til tappelinjer, og tallene $2K+1, \ldots , 2 K + N$ svarer til samlinger. Der er højst ét rør mellem hvert par af forbindelsespunkter. Vi ved også at $1 \leq C_ i \leq 10^9$.

Derudover garanteres det, at hvert ølkar og hver tappelinje forbinder til præcis ét rør.

Output

Hvis der ikke findes en gyldig konfiguration, udskriv da »Expand brewery«. Ellers udskrives et enkelt heltal: mængden af hver øl der brygges i den bedste gyldige konfiguration.

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