/*
 * COmplexitate timp: O(n * m^2)
 *
 * Algoritm folosit: Edmonds-Karp
 * */
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream in("maxflow.in");
ofstream out("maxflow.out");
class Flow
{
    int source, sink;
    int n;
    int maxFlow;
    std::vector<bool> visited;
    std::vector<std::vector<int> > graph;
    std::vector<int> father;

    struct Edge {
        int from, to, flow;
    };

    Edge edges[200002];
    int edgeCount;

    void dfs(int k){        //  dfs pentru a afla ce noduri sunt accesibile din sursa, folosit pentru minCut
        visited[k] = true;
        for (int i : graph[k]) {
            if (!visited[edges[i].to] && edges[i].flow) {       //  daca nu am vizitat nodul si exista un flux pe muchie
                dfs(edges[i].to);
            }
        }
    }

    bool bfs()
    {
        visited.assign(n+1, false);
        std::queue<int> q;
        q.push(source);
        visited[source] = true;

        while(!q.empty())
        {
            int node = q.front();
            q.pop();

            for(int edgeID : graph[node])           //  iau ID-ul muchiei incidente cu node
            {
                Edge const &e = edges[edgeID];
                int to = e.to;                      //  nodul de la capatul muchiei
                if(!e.flow || visited[to])
                    continue;                       //  daca muchia e saturata sau am vizitat deja nodul, nu o mai iau in considerare
                visited[to] = true;
                q.push(to);                      //  adaug nodul in coada
                father[to] = edgeID;                //  tatal nodului este ID-ul muchiei care provine din node
                if(to == sink)
                    return true;                    //  daca am ajuns la sink, am gasit un drum
            }
        }
        return false;
    }


public:
    Flow(int n, int source, int sink)
    {
        this->source = source;
        this->sink = sink;
        this->n = n;
        this->maxFlow = 0;
        this->edgeCount = -1;           //  muchiile vor fi indexate de la 0
        graph.resize(n + 1);
        visited.resize(n + 1);
        father.resize(n + 1);
    }

    void addEdge(int x, int y, int cost = 1)
    {
        // Muchia (x, y) vine inainte de muchia (y, x), sunt indexate par si impar, astfel facnd xor cu 1 obtinem muchia opusa

        graph[x].push_back(++edgeCount);        //  adaug ID-ul muchiei in lista de adiacenta a nodului x
        edges[edgeCount].from = x;
        edges[edgeCount].to = y;
        edges[edgeCount].flow = cost;

        graph[y].push_back(++edgeCount);        //  adaug ID-ul muchiei de intoarcere in lista de adiacenta a nodului y
        edges[edgeCount].from = y;
        edges[edgeCount].to = x;
        edges[edgeCount].flow = 0;
    }

    int getMaxFlow()
    {
        maxFlow = 0;
        do{
            if( !bfs() )        //  daca nu am gasit drum de la source la sink, am terminat
                break;
            for (auto edgeID : graph[sink]) {               //  parcurg muchiile incidente cu sink
                int to = edges[edgeID].to;                      //  nodul de la capatul muchiei
                if(!edges[edgeID ^ 1].flow || !visited[to])     //  daca muchia (de la "to" la sink) e saturata sau nu am vizitat nodul, trec la urmatorul nod
                    continue;

                father[sink] = edgeID ^ 1;                      //  tatal sink-ului este ID-ul muchiei (to, sink); edgeID este muchia de intoarcere (sink, to)
                int flowMin = 0x7fffffff;
                for (int i = sink; i != source; i = edges[father[i]].from)  //  parcurg drumul de la sink la source cautand bottleneck-ul
                    flowMin = std::min(flowMin, edges[father[i]].flow);
                if (flowMin == 0)
                    continue;           //  daca nu am gasit un flux minim, trec la urmatorul nod

                maxFlow += flowMin;
                for (int i = sink; i != source; i = edges[father[i]].from) {        //  parcurg drumul de la sink la source si actualizez fluxul
                    edges[father[i]].flow -= flowMin;           //  scad fluxul minim pe drumul de ameliorare
                    edges[father[i] ^ 1].flow += flowMin;       //  maresc cu fluxul minim pe drumul opus
                }
            }
        } while (true);
        return maxFlow;
    }

    int getFlow() const{
        return maxFlow;
    }

    std::vector<std::pair<int, int>> getMinCut()
    {
        visited.assign(n+1, false);
        unsigned int flow = 0;      //  mica optimizare... taietura minima = fluxul maxim, deci ma opresc cand am gasit taieturile minime
        //  parcurg graful cu dfs pentru a afla nodurile accesibile din sursa
        dfs(source);
        std::vector<std::pair<int, int>> minCut;        //  muchiile care fac parte din minCut
        for (int i = source; i <= sink && flow < maxFlow; ++i) {          //  parcurg nodurile din intervalul [source, sink]
            if (visited[i]) {       //  daca nodul e accesibil din sursa
                for (int j: graph[i]) {
                    if (!visited[edges[j].to] && !edges[j].flow) {
                        minCut.emplace_back(i, edges[j].to);
                        flow += edges[j ^ 1].flow;          //  preiau fluxul de pe muchia de intoarcere
                    }
                }
            }
        }
        return minCut;
    }
};

int main() {
    int n, m;
    in >> n >> m;
    Flow f(n, 1, n);

    while (m--) {
        int x, y, c;
        in >> x >> y >> c;
        f.addEdge(x, y, c);
    }
    in.close();

    int sol = f.getMaxFlow();

    out << sol << '\n';

    /*
     *  B
     * */

    auto minCut = f.getMinCut();
    for (auto edge : minCut) {
        out << edge.first << ' ' << edge.second << '\n';
    }

    out.close();
    return 0;
}