#include <bits/stdc++.h>
// #pragma optimize ("O3")
// #pragma optimize("unroll-loops,fast-math")
// #pragma target ("avx2,bmi2,popcnt,lzcnt")

#define int long long
#define pii pair<int, int>
#define fs first
#define sd second

using namespace std;

const string fileName = "maxflow";
ifstream in(fileName + ".in");
ofstream out(fileName + ".out");

struct edge {
    int fs, sd;
    int node;
} edges[10005];
int flow[1005];
vector<int> g[5005];
int n, m, u, v, c;
int maxflow;

void dfs(int node, int parent, int mxflw) {
        if(node == n) {
            maxflow += mxflw;
            return;
        }
        // merg prin toti vecinii si vad prin care am voie sa ma plimb
        // eventual notez ca nu am voie la parent
        for(auto link : g[node]) {
            if(edges[link].node == parent || edges[link].node == 1)
                continue;
            if(node == 1)
                mxflw = 1e12;
            // crtedge este edges[link]
            if(link % 2 == 0) {
                if(flow[node] && edges[link].fs < edges[link].sd) {
                    if(mxflw < edges[link].sd - edges[link].fs) {
                        if(mxflw < flow[node]) ;
                        else mxflw = flow[node];
                        // edges[link].fs += mxflw;
                        // edges[link + 1].fs -= mxflw;
                    }
                    else {
                        mxflw = edges[link].sd - edges[link].fs;
                        if(mxflw < flow[node]) ;
                        else mxflw = flow[node];
                        // edges[link].fs += mxflw;
                        // edges[link + 1].fs -= mxflw;
                    }
                    edges[link].fs += mxflw;
                    edges[link + 1].fs -= mxflw;
                    flow[edges[link].node] += mxflw;
                    flow[node] -= mxflw;
                    dfs(edges[link].node, node, mxflw);
                }
            }
            // auxedge este edges[link + 1]
            else {
                if(flow[node] && edges[link].fs < edges[link].sd) {
                    if(mxflw < edges[link].sd - edges[link].fs) {
                        if(mxflw < flow[node]) ;
                        else mxflw = flow[node];
                        // edges[link].fs += mxflw;
                        // edges[link + 1].fs -= mxflw;
                    }
                    else {
                        mxflw = edges[link].sd - edges[link].fs;
                        if(mxflw < flow[node]) ;
                        else mxflw = flow[node];
                        // edges[link].fs += mxflw;
                        // edges[link + 1].fs -= mxflw;
                    }
                    edges[link].fs += mxflw;
                    edges[link + 1].fs -= mxflw;
                    flow[edges[link].node] += mxflw;
                    flow[node] -= mxflw;
                    dfs(edges[link].node, node, mxflw);
                }
            }
        }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    in.tie(NULL); out.tie(NULL);

    // facem maxflow
    in >> n >> m;
    for(int i = 0; i < m; i++) {
        in >> u >> v >> c;
        // am muchie de la u la v cu capacitatea c
        // muhcia i * 2 si i * 2 + 1 va fi ce pun la g[u]
        edges[i * 2] = {0, c, v};
        edges[i * 2 + 1] = {0, 0, u};
        g[u].push_back(i * 2);
        g[v].push_back(i * 2 + 1);
    }
    // nodul meu source va fi 1 si nodul sink va fi n
    // fac varianta de baza: fac dfs
    flow[1] = 1e12;
    dfs(1, 0, 1e12);

    out << flow[n] << '\n';
    // out << maxflow << '\n';

    for(int i = 1; i <= n; i++) {
        cout << i << '\n';
        for(auto link : g[i]) {
            cout << edges[link].fs << ' ' << edges[link].sd << ' ' << edges[link].node << '\n';
        }
        cout << '\n';
    }

    return 0;
}