Problem E
Engaging with Loyal Customers

On the occasion of its $10$-year anniversary, an e-commerce company is running a campaign to engage with their loyal customers. They have prepared $m$ gifts, numbered from $1$ to $m$, to thank its loyal customers where each customer will receive no more than one gift. The company has $n$ loyal customers, numbered from $1$ to $n$. In order to ensure that customers are satisfied with the gift they receive, the company decided to conduct a customer survey. The customer survey result is recorded by the feedback cards, each of which can be described by a tuple of three positive integers $(i,j,p)$ indicating that customer $i$ has a satisfaction level of $p$ if he or she receives the gift $j$. Each customer will give his or her level of satisfaction for every gift unless he/she has a satisfaction level of $0$. At the end, the company receives $k$ feedback cards from their loyal customers.

Based on the result of the customer survey, your task is to determine how to send gifts to loyal customers to bring the greatest sum of satisfaction of all customers receiving the gifts.

Input

• The first line contains three integers $m$, $n$, $k$ $(1 \leq m,n \leq 1\, 000, \; 1 \leq k \leq m \times n)$;

• The next $k$ lines describe the customer survey results, each of which contains three positive integers $i, j, p$ described above $(1 \leq i \leq n, \; 1 \leq j \leq m, \; 1 \leq p \leq 30\, 000)$. It is guaranteed that no $2$ surveys have same $i$ and $j$.

Output

• The first line contains an integer that is the greatest sum of satisfaction of all customers;

• The second line contains the integer $s$ – the number of gifts that must be sent to the customers;

• The next $s$ lines describe how the gifts are sent: each line contains two integers $x,y$ indicating that the customer $x$ receives the gift $y$.

If there are more than one solutions giving the greatest sum of satisfaction, you can print any of them.

3 2 4
1 1 2
1 2 3
1 3 5
2 3 8

11
2
1 2
2 3