Problem F
Faires Brauen

Biertanks in einer Brauerei in Georgia, USA. Public Domain, Paul Brennan

United Brewery entstand durch die Fusion und den Zusammenschluss verschiedener kleiner und lokaler Brauereien, die jeweils ihre eigenen Biersorten herstellten. Da die Rezepte dieser Brauereien bei den örtlichen Fans sehr beliebt waren, beschloss die United Brewery, die Tradition aufrechtzuerhalten, indem sie von jeder Biersorte eine identische Menge produzierte und vertrieb. Und um Unruhen zwischen den verschiedenen Fangemeinden zu vermeiden, wurde der Grundsatz der Fairness eingeführt: Von jedem Bier wird die gleiche Menge gebraut und vertrieben.

Das Ziel der Brauerei besteht natürlich darin, die größtmögliche Gesamtmenge an Bier zu produzieren. Dies stellte sich jedoch aufgrund der begrenzten Produktionskapazitäten der United Brewery als eine herausfordernde Aufgabe heraus.

Die Produktionsanlagen der United Brewery bestehen aus einem Tank und einer Abfüllanlage pro Biersorte, sowie internen Verbindungspunkte. Rohre führen jeweils paarweise von einem dieser Komponenten zu einem anderen. Hier ist ein Beispiel mit 3 Biersorten und 4 Verbindungen, das zum ersten Beispiel-Input korrespondiert:

Jeder Tank und jede Abfüllanlage wird an genau ein Rohr angeschlossen, aber mehrere Rohre können an dieselbe Verbindung angeschlossen sein. Jeder Verbindungspunkt kann so konfiguriert werden, dass intern disjunkte Paare von einfallenden Rohren ohne weitere Einschränkungen verbunden werden. Es gibt zum Beispiel $3$ Konfigurationsmöglichkeiten, innerhalb desselben $5$-Verbindungspunkt die Rohre zu verbinden:

Durch eine geeignete Auswahl der Verbindungen kann das Bier von den Biertanks zu den einzelnen Abfüllanlagen fließen. Die Kapazität jedes Rohrs begrenzt die Biermenge, die hindurchfließen kann. Die in einer gültigen Konfiguration erzeugte Biermenge ist die Mindestkapazität über alle Rohre, durch die das Bier in dieser Konfiguration fließt.

Input

Die erste Zeile des Inputs besteht aus $3$ Integern: die Anzahl  $K$ von Biertanks und Abfüllanlagen, wobei $2 \leq K \leq 10$, die Anzahl $N$ von Verbindungen, wobei $0 \leq N \leq 1000$, und die Anzahl $M$ an Rohren, wobei $K \leq M \leq 10^4$.

Die darauf folgenden $M$ Zeilen beinhalten 3 Integer $A_ i$, $B_ i$, und $C_ i$, welche die Rohre Beschreiben: Das $i$-te Rohr verbindet $A_ i$ mit $B_ i$ und hat Kapazität $C_ i$. Hierbei sind $A_ i$ und $B_ i$ verschiedene Verbindungspunkte. Jeder Verbindungspunkt ist eine Nummer von $1$ bis $2K+N$, wobei $1, \ldots , K$ die Biertanks repräsentieren, $K+1, \ldots , 2 K$ die Abfüllanlagen repräsentieren und $2K+1, \ldots , 2 K + N$ Verbindungen darstellen. Es gibt höchstens ein Rohr zwischen jedem Verbindungspunkt-Paar. Zudem wissen wir, das $1 \leq C_ i \leq 10^9$ hält.

Jeder Biertank und jede Abfüllanlage ist mit genau einem Rohr verbunden.

Output

Falls es nicht um eine gültige Konfiguration handelt, gib “Expand brewery” aus. Sonst gib die Menge aus, die jeweils von jeder Biersorten produziert wird.

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