#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("terenuri3d.in");
ofstream cout("terenuri3d.out");
#define MAXN 655
#define INF 0x3f3f3f3f

queue<int> coada;
vector<int> graf[MAXN];
vector< pair<int, int> > rasp3;
int capacitate[MAXN][MAXN], cost[MAXN][MAXN], flux[MAXN][MAXN], dist[MAXN], dist_vechi[MAXN], tata[MAXN], maxTaran[MAXN], maxCasa[MAXN+300], aux[MAXN][MAXN];
int n, m, k, i, j, x, y, z, st, fin, flux_crt, flux_total, cost_total, cost_crt,rasp2, rasp2_aux;
bool fol[MAXN], fol2[MAXN];

void afisare()
{
    for(i=st; i<=fin; i++)
    {
        cout<<i<<": ";
        for(j=0; j<graf[i].size(); j++)
            cout<<"( "<<graf[i][j]<<", "<<capacitate[i][ graf[i][j] ]<<", "<<cost[i][ graf[i][j] ]<<" ) ";
        cout<<"\n";
    }
}

bool Bellman(int st, int fin)
{
    int crt, urm, i;
    for(i=st; i<=fin; i++)
    {
        dist[i] = INF;
        tata[i] = 0;
    }

    dist[st] = 0;
    coada.push(st);
    while(!coada.empty())
    {
        crt = coada.front(); coada.pop();

        for(i=0; i<graf[crt].size(); i++)
        {
            urm = graf[crt][i];
            if(dist[urm] > dist[crt] + cost[crt][urm] && capacitate[crt][urm] > 0 )
            {
                dist[urm] = dist[crt] + cost[crt][urm];
                tata[urm] = crt;
                coada.push( urm );
            }
        }
    }
    if(tata[fin])
        return 1;
    return 0;
}
int main()
{
    cin >> n >> m >> k; // n tarani, m case, k dorinte

    st = 1; fin = n + m + 2;
    for(i=1; i<=k; i++)
    {
        cin >> x >> y >> z ; // taranul x vrea casa y si primeste fericire z

        x++; y += n+st;
        if( !maxTaran[x] )
        {
           graf[st].push_back(x);
           graf[x].push_back(st);
        }
        if( !maxCasa[y] )
        {
            graf[y].push_back(fin);
            graf[fin].push_back(y);
        }

        graf[x].push_back(y);  graf[y].push_back(x);
        cost[x][y] = -z; cost[y][x] = z;
        capacitate[x][y] = 1;

        maxTaran[x] = max(maxTaran[x], z);
        maxCasa[y] = max(maxCasa[y], z);
    }

    for(i=2; i<=n+1; i++)
        capacitate[st][i] = 1;

    for(i=1; i<=m; i++)
        capacitate[i+n+st][fin] = 1;

    for(i=2; i<=n+1; i++)
    {
        for(j=0; j<graf[i].size(); j++)
        {
            int urm = graf[i][j];
            if(urm == st)
                continue;

            capacitate[i][urm] = 1;
        }
    }

    for(i=st; i<=fin; i++)
        for(j=st; j<=fin; j++)
            aux[i][j] = capacitate[i][j];

    while( Bellman(st, fin) )
    {
        flux_crt = INF;
        cost_crt = 0;
        for(i=fin; i!=st && i; i=tata[i])
            flux_crt = min(flux_crt, capacitate[tata[i]][i]);

        if(flux_crt)
        {
            x=0;
            for(i=fin; i!=st; i=tata[i])
            {
                x++;
                capacitate[tata[i]][i] -= flux_crt;
                capacitate[i][tata[i]] += flux_crt;
                cost_crt += cost[tata[i]][i];
            }

            flux_total += flux_crt;
            if(cost_crt<0)
            {
                cost_total -= cost_crt;
                rasp2++;
                if(rasp2==209)
                    break;

            }
        }
    }
    cout<<cost_total<<"\n"<<rasp2;
    cout<<"\n";

    for(i=st; i<=fin; i++)
        for(j=st; j<=fin; j++)
            capacitate[i][j] = aux[i][j];

    while( Bellman(st, fin) )
    {
        flux_crt = INF;
        cost_crt = 0;
        for(i=fin; i!=st && i; i=tata[i])
            flux_crt = min(flux_crt, capacitate[tata[i]][i]);

        if(flux_crt)
        {
            x=0;
            for(i=fin; i!=st; i=tata[i])
            {
                x++;
                capacitate[tata[i]][i] -= flux_crt;
                capacitate[i][tata[i]] += flux_crt;
                cost_crt += cost[tata[i]][i];
            }

            if(cost_crt<0)
            {
                rasp2_aux++;
                if(rasp2_aux == rasp2)
                    break;

            }
        }
    }

    for(i=2; i<=n+1; i++)
    {
        for(j=0; j<graf[i].size(); j++)
        {
            int urm = graf[i][j];
            if(capacitate[i][urm] == 0 && urm-n-1 > 0 )
                cout<<i-1<<" "<<urm-n-1<<"\n";
        }
    }
}