#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("terenuri3d.in");
ofstream g("terenuri3d.out");

#define nmax 252
#define inf (1<<29)
#define ll long long

int n, m, K, capac[nmax*2][nmax*2], flux[nmax*2][nmax*2], dist[nmax*2];
bool viz[nmax*2];
int q[nmax*2], t[nmax*2], rez[nmax*2][2], rez2[nmax*2][2];
int Sz, Sum2;
vector< pair<int,int> > gf[nmax*2];

void citeste(){
    f >> n >> m >> K;
    int x, y, z;
    for(int i=1; i<=K; ++i){
        f >> x >> y >> z; z = -z;
        gf[x].push_back( make_pair( y+n, z ) );
        gf[y+n].push_back( make_pair( x, -z ) );
        capac[x][y+n] = 1;
        //capac[y+n][x] = 1;
    }
}

inline bool Bf(int s, int d){
    for(int i=0; i<=n+m+1; ++i) viz[i] = 0, dist[i] = inf, t[i] = 0;
    dist[s] = 0;
    viz[s] = 1;
    int st = 1; int dr = 1;
    q[st] = s;
    for(; st<=dr; ){
        int nod = q[st]; ++st;
        viz[nod] = 0;
        for(int i=0; i<gf[nod].size(); ++i){
            int vc = gf[nod][i].first; int cost = gf[nod][i].second;
            //cout << vc << " ";
            // vreau sa bag pe nod -> vc
            //cout << nod << " " << vc << " " << capac[nod][vc] << " " << cost<< "\n";
            if ( capac[nod][vc] > flux[nod][vc] && dist[vc] > dist[nod] + cost ){
                //cout << vc << "\n";
                t[vc] = nod;
                //cout << vc << " " << nod << " " << dist[nod] + cost << "\n";
                dist[vc] = dist[nod] + cost;
                if (viz[vc] == 0){
                    //cout << vc << " ";
                    viz[vc]=1; q[++dr] = vc;
                }
            }
        }
    }
    if (dist[d] != inf) return 1;
    return 0;

}

void aflaRaspuns(){
    // ma uit in muchiile saturate
    int Sum = 0; int sz = 0;
    for(int i=1; i<=n; ++i){
        for(int j=0; j<gf[i].size(); ++j){
            int vc = gf[i][j].first; int cost = gf[i][j].second;
            //cout << capac[i][vc] << " " << flux[i][vc] << "\n";
            if (flux[i][vc] == capac[i][vc] && capac[i][vc] > 0 && vc != n+m+1 && i != n+m+1){// e saturata
                //cout << "mumu";
                Sum += cost; rez[++sz][0] = i; rez[sz][1] = vc-n;
            }
        }
    }
    for(int i=n+1; i<=n+m; ++i){
        for(int j=0; j<gf[i].size(); ++j){
            int vc = gf[i][j].first; int cost = gf[i][j].second;
            //cout << capac[i][vc] << " " << flux[i][vc] << "\n";
            if (flux[i][vc] == capac[i][vc] && capac[i][vc] > 0 && vc != n+m+1 && i != n + m +1){
                //cout << "mumu";
                Sum += cost; rez[++sz][0] = vc; rez[sz][1] = i-n;
            }
        }
    }
    //cout << Sum << "\n";
    if (Sum*-1 > Sum2){
        Sum2 = Sum*-1;
        for(int i=1; i<=sz; ++i){
            rez2[i][0] = rez[i][0]; rez2[i][1] = rez[i][1];
        }
        Sz = sz;
    }
}


void bagaFlux(int s, int d){
    //Bf(s, d);

    for(; Bf(s, d); ){
        // aleg muchia minima de pe drum;
        int Min = inf;
        //cout << "mumu";
        for(int i=d; i!=s; i=t[i]){
            //cout << i << " " << t[i] << "\n";
            // m-am dus pe muchia t[i] - > i
            Min = min(Min, capac[ t[i] ][i] - flux[ t[i] ][i]);
        }
        //cout << Min << "\n";
        //acum bag fluxul
        for(int i=d; i!=s; i=t[i]){
            // bag flux pe t[i] - > i; si il intorc pe i->t[i];
            flux[ t[i] ][i] += Min;
            flux[i][ t[i] ] -= Min;
        }
        aflaRaspuns();
        //cout << "mumu";
    }
    g << Sum2 << "\n";
    g << Sz << "\n";
    for(int i=1; i<=Sz; ++i){
        g << rez2[i][0] << " "<< rez2[i][1] << "\n";
    }
}

void rezolva(){
    // ideea ar fi asa eu am nevoie de un cuplaj de cost Maxim;
    // pt asta il aflu asa : bag o sursa fie el nodul 0; si o destinatie fie el nodul n + m + 1; iar graful mi-l fac in felul urmator:
    // o sa am taranii si casele; casele le renumerotez o casa y va fi n + y;
    // si bag flux de cost maxim; dupa ce bag fluxul raspunsul va fi suma costurilor de pe muchiile saturate
    for(int i=1; i<=n; ++i){
        gf[0].push_back( make_pair(i, 0) );// leg sursa de fiecare taran si ii pun capactiatea 1
        gf[i].push_back( make_pair(0, 0) );
        capac[0][i] = 1;
    }
    for(int i=1; i<=m; ++i){
        gf[i+n].push_back( make_pair(n+m+1, 0) );// leg destiantia
        gf[n+m+1].push_back( make_pair( n+m+1, 0 ) );
        capac[i+n][n+m+1] = 1;
    }

    bagaFlux(0, n+m+1);
    //aflaRaspuns();
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}