#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <queue>
#include <cstring>
#include <set>
#include <cctype>
using namespace std;

#ifdef INFOARENA
#define ProblemName "cmcm"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

template <class T> void readNum(T &nr) {
	nr = 0;
	T sign = 1;
	char c;
	while (!isdigit(c = getchar()))
		(c == '-') && (sign = -1);
	do {
		nr = nr * 10 + c - '0';
	} while (isdigit(c = getchar()));
	nr *= sign;
}

class graph {
private:
	vector< vector<int> > ngh;
	vector< vector<int> > F;
	vector< vector<int> > C;
	vector< vector<int> > W;
	int source, sink;
public:
	graph(int N, int _source, int _sink) {
		ngh.resize(N);
		source = _source; sink = _sink;
		F.resize(N, vector<int>(N, 0));
		C.resize(N, vector<int>(N, 0));
		W.resize(N, vector<int>(N, 0));
	}
	void insertEdge(int n1, int n2, int c, int w) {
		ngh[n1].push_back(n2);
		ngh[n2].push_back(n1);
		C[n1][n2] = c;
		W[n1][n2] = w;
		W[n2][n1] = -w;
	}

	void BellmanFord(vector<int> &dist) {
		int N = ngh.size();
		memset(&dist[0], 0x3F, dist.size() * sizeof(dist[0]));
		dist[source] = 0;
		queue<int> Q;
		vector<char> inQueue(N, 0);
		inQueue[source] = 1;
		Q.push(source);
		while (!Q.empty()) {
			int t = Q.front();
			Q.pop();
			inQueue[t] = 0;
			for (auto i : ngh[t])
			if (C[t][i] && dist[t] + W[t][i] < dist[i]) {
				dist[i] = dist[t] + W[t][i];
				if (!inQueue[i]) {
					inQueue[i] = 1;
					Q.push(i);
				}
			}
		}
	}
	void Dijkstra(vector<int> &adjustedDist, vector<int> &oldDist, vector<int> &realDist, vector<char> &visited, vector<int> &prev) {
		int N = ngh.size();
		memset(&prev[0], 0xFF, prev.size() * sizeof(prev[0]));
		memset(&realDist[0], 0x3F, realDist.size() * sizeof(realDist[0]));
		memset(&adjustedDist[0], 0x3F, adjustedDist.size() * sizeof(adjustedDist[0]));
		memset(&visited[0], 0, visited.size());
		adjustedDist[source] = realDist[source] = 0;
		priority_queue< pair<int, int> > Q;
		Q.push(make_pair(0, source));
		while (!Q.empty()) {
			int t = Q.top().second;
			Q.pop();
			if (visited[t])
				continue;
			visited[t] = 1;
			for (auto i : ngh[t])
			if (C[t][i] > F[t][i]) {
				int newAdjustedDistance = adjustedDist[t] + W[t][i] + oldDist[t] - oldDist[i];
				assert(W[t][i] + oldDist[t] - oldDist[i] >= 0);
				if (newAdjustedDistance < adjustedDist[i]) {
					Q.push(make_pair(-newAdjustedDistance, i));
					adjustedDist[i] = newAdjustedDistance;
					realDist[i] = realDist[t] + W[t][i];
					prev[i] = t;
				}
			}
		}
	}
	pair<int, int> FordFulkerson() {
		int N = ngh.size();
		vector<int> oldist(N);
		BellmanFord(oldist);

		vector<int> dist(N);
		vector<int> prev(N);
		vector<int> realDist(N);
		vector<char> visited(N);
		int totalCost = 0;
		int totalFlow = 0;
		while (true) {
			Dijkstra(dist, oldist, realDist, visited, prev);
			if (prev[sink] == -1)
				break;
			int minToSend = 0x3F3F3F3F;
			int curNod = sink;
			while (prev[curNod] != -1) {
				if (C[prev[curNod]][curNod] - F[prev[curNod]][curNod] < minToSend)
					minToSend = C[prev[curNod]][curNod] - F[prev[curNod]][curNod];
				curNod = prev[curNod];
			}
			curNod = sink;
			while (prev[curNod] != -1) {
				F[prev[curNod]][curNod] += minToSend;
				F[curNod][prev[curNod]] -= minToSend;
				curNod = prev[curNod];
			}
			totalFlow += minToSend;
			totalCost += minToSend * realDist[sink];
			memcpy(&oldist[0], &realDist[0], oldist.size() * sizeof(oldist[0]));
		}
		return make_pair(totalFlow, totalCost);
	}
	void printMatching(int N) {
		for (int i = 1; i <= N; i++)
		for (auto j : ngh[i])
		if (F[i][j]) {
			printf("%d %d\n", i, j - N);
			break;
		}
	}
};

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	int N, M, E;
	readNum(N); readNum(M); readNum(E);
	int sink = N + M + 1;
	graph G(N + M + 2, 0, sink);
	while (E--) {
		int n1, n2, w;
		readNum(n1); readNum(n2); readNum(w);
		G.insertEdge(n1, n2 + N, 1, w);
	}
	for (int i = 1; i <= N; i++)
		G.insertEdge(0, i, 1, 0);
	for (int j = N + 1; j <= M + N; j++)
		G.insertEdge(j, sink, 1, 0);
	pair<int, int> aux = G.FordFulkerson();
	printf("%d %d\n", aux.first, aux.second);
	G.printMatching(N);
	return 0;
}