#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

#define pb push_back
#define iterator vector<int>::iterator

const int NMAX = 1024;
const int INF = 1 << 30;
const char iname[] = "maxflow.in";
const char oname[] = "maxflow.out";

int capacitate[NMAX][NMAX];
int flux[NMAX][NMAX];
int tata[NMAX];
int viz[NMAX];
vector<int> graf[NMAX];
int n, m;

bool BF()
{
    int sursa = 1,  q[NMAX];
    memset(viz, 0, (n+5)*sizeof(int));
    q[0] = 1;
    q[1] = 1;
    viz[sursa] = 1;
    for(int j = 1; j <= q[0]; j++)
    {
        int nod = q[j];
        if(nod != n)
        for(iterator it = graf[nod].begin(); it != graf[nod].end(); ++it)
        {
            if(!viz[*it] && flux[nod][*it] < capacitate[nod][*it])
            {
                viz[*it] = 1;
                tata[*it] = nod;
                q[ ++q[0] ] = *it;
            }
        }
    }
    return viz[n];
}

int main()
{
    ifstream f(iname);
    f >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        f >> x >> y >> z;
        capacitate[x][y] += z;
        graf[x].pb(y);
        graf[y].pb(x);
    }
    while(BF())
    {
        for(iterator vn = graf[n].begin(); vn != graf[n].end(); ++vn)
        {
            if(flux[*vn][n] == capacitate[*vn][n] || !viz[*vn]) continue;
            tata[n] = *vn;
            int fmin = INF;
            for(int y = n; y != 1; y = tata[y])
                {
                    if(capacitate[tata[y]][y] - flux[tata[y]][y] < fmin)
                        fmin = capacitate[tata[y]][y] - flux[tata[y]][y];
                    cout<<y<<' '<<tata[y]<<'\n';
                }
            if(fmin == 0) continue;
            for(int y = n; tata[y]; y = tata[y])
            {
                flux[tata[y]][y] += fmin;
                flux[y][tata[y]] -= fmin;
            }
        }
    }
    int fluxMax = 0;
    for(iterator it = graf[1].begin(); it != graf[1].end(); ++it)
        fluxMax += flux[1][*it];
    ofstream g(oname);
    g << fluxMax;
    return 0;
}