#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T> pair<T, vector<int>>
weighted_matching(vector<vector<T>> &C) {
    int i = sz(C), m = sz(C[0]), c, j, s, r;
    vector<T> dist(m), potential(m);
    vi row_match(i), col_match(m, -1), cols(m), prev(m);
    T d, nd, cost = 0;
    for (; i--;) {
        rep(c, 0, m) dist[c] = C[i][c], cols[c] = c, prev[c] = i;
        for (s = 0;;) {
            for (j = s; j < m; j++) if (c = cols[j],
                nd = dist[c] - potential[c], j == s || d > nd)
                d = nd, swap(cols[s], cols[j]);
            if (!~(r = col_match[c = cols[s++]])) break;
            rep(j, 0, m) if (dist[j] > (nd = C[r][j] - C[r][c] +
                dist[c])) dist[j] = nd, prev[j] = r;
        }
        for (cost += dist[c]; s--;) j = cols[s],
            potential[j] = dist[j] - d;
        for (; r != i; swap(c, row_match[r]))
            r = col_match[c] = prev[c];
    }
    return {cost, row_match};
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int n, m, k;
	cin >> m >> n >> k;
	bool swapped = 0;
	if (n < m) swap(n, m), swapped = 1;
	vector<vector<int>> cost(m, vector<int>(n, 0));
	rep(_, 0, k) {
		int i, j, p;
		cin >> i >> j >> p;
		i--; j--;
		if (!swapped) swap(i, j);
		cost[i][j] = -p;
	}
	auto [c, matching] = weighted_matching(cost);
	vector<pii> ans;
	rep(i, 0, sz(matching)) {
		pii p = pii(i, matching[i]);
		if (!swapped) swap(p.first, p.second);
		ans.emplace_back(p);
	}
	cout << -c << "\n";
	cout << sz(ans) << "\n";
	for (pii& e : ans) cout << e.first + 1 << " " << e.second + 1 << "\n";
}