#include <fstream>
#include <vector>
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

ifstream inf("maxflow.in");
ofstream outf("maxflow.out");

const int NMAX = 1000;

vector<int> ad[NMAX];
int flow[NMAX][NMAX];
int cap[NMAX][NMAX];
int pred[NMAX];

int main() {
    int n, m, x, y, c;
    inf >> n >> m;
    for(int i = 0; i < m; i++) {
        inf >> x >> y >> c;
        x--;
        y--;
        ad[x].push_back(y);
        ad[y].push_back(x);
        cap[x][y] += c;
    }

    int ftot = 0;
    do {
        memset(pred, 0xff, sizeof(pred));
        queue<int> q;
        q.push(0);
        while(!q.empty()) {
            x = q.front();
            q.pop();
            for(int el : ad[x]) {
                if(pred[el] == -1 && flow[x][el] < cap[x][el]) {
                    pred[el] = x;
                    q.push(el);
                }
            }
        }
        if(pred[n - 1] != -1) {
            int fmin = 0x3f3f3f3f;
            for(int x = n - 1; x; x = pred[x]) {
                fmin = min(fmin, cap[pred[x]][x] - flow[pred[x]][x]);
            }
            for(int x = n - 1; x; x = pred[x]) {
                flow[pred[x]][x] += fmin;
                flow[x][pred[x]] -= fmin;
                cout << pred[x] << ' ' << x << '\n';
            }
            ftot += fmin;
        }

    } while(pred[n - 1] != -1);

    outf << ftot;
    return 0;
}