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

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int nodes, edges, s, t;
vector<int> father;
vector<vector<int>> capacity;
vector<vector<int>> graph;
vector<vector<int>> edg;
long cost_minn=0;


void read(){
    fin>>nodes>>edges;
    s=1;
    t=nodes;
    graph.resize(nodes+1);
    father.resize(nodes+1);
    capacity.resize(nodes+1, vector<int>(nodes+1));

    for(int i=0;i<edges;i++){
        int x, y;
        long cost;
        fin>>x>>y>>cost;
        edg.push_back({x,y,cost});
        graph[x].push_back(y);
        graph[y].push_back(x);
        capacity[x][y]=cost;
    }

}

bool bfs(){
    vector <bool> viz(nodes+1);
    queue<int> q;
    q.push(s);
    viz[s]=true;
    father[s]=-1;
    while(!q.empty()){
        int current_node = q.front();
        q.pop();
        for(auto adj: graph[current_node]){
            if(!viz[adj] && capacity[current_node][adj]){
                father[adj]=current_node;
                if(adj==t){
                    return true;
                }
                viz[adj]=true;
                q.push(adj);
            }
        }
    }
    return false;
}

int edmondsKarp(){
    long flux_max=0;
    while(bfs()){
        int x, y, path_min=INT_MAX;
        for(x=t;x!=s;x=father[x]){
            y=father[x];
            if(capacity[y][x] < path_min){
                path_min=capacity[y][x];
            }
        }
        for(x=t;x!=s;x=father[x]){
            y=father[x];
            capacity[y][x] -= path_min;
            capacity[x][y] += path_min;
        }
        flux_max += path_min;

    }
    return flux_max;
}

int main(){
    read();
    fout<<edmondsKarp();
    for(int i=2;i<=6;i++){
        for(auto node: graph[i]){
            if(node!=1 && capacity[i][node]==0 && node!=11){
                cout<<i<<" "<<node<<"\n";
            }
        }
    }
    return 0;
}