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

using namespace std;

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

int n, m, a, b, c, flux[1001][1001], viz[1001], t[1001], tot;
vector<vector<int>> ad;

bool bfs(){
    queue<int> q;
    q.push(1);
    for (int i = 0; i < n + 1; ++i) {
        t[i] = 0;
    }
    for (int i = 0; i < n + 1; ++i) {
        viz[i] = 0;
    }
    viz[1] = 1;

    while(!q.empty()){
        int x = q.front();
        q.pop();
        for (int i = 0; i < ad[x].size(); ++i) {
            if (viz[ad[x][i]] == 0 && flux[x][ad[x][i]] > 0){
                t[ad[x][i]] = x;
                q.push(ad[x][i]);
                viz[ad[x][i]] = 1;
                if (ad[x][i] == n)
                    return 1;
            }
        }
    }
    return 0;
}

int main() {
    fin>>n>>m;
    ad.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        fin>>a>>b>>c;
        ad[a].push_back(b);
        ad[b].push_back(a);
        flux[a][b] = c;
    }

    while (bfs()){
        for (int i = 0; i < ad[n].size(); ++i) {
            if (viz[ad[n][i]]){
                int minn = INT_MAX;
                int x = n;
                while(x != 1){
                    minn = min(minn, flux[t[x]][x]);
                    x = t[x];
                }
                x = n;
                while(x != 1){
                    flux[t[x]][x] = flux[t[x]][x] - minn;
                    flux[x][t[x]] = flux[x][t[x]] + minn;
                    x = t[x];
                }
                tot = tot + minn;
            }
        }
    }
    fout<<tot;
    for (int i = 1; i < ad.size(); ++i) {
        cout<<i<<": ";
        for (int j = 0; j < ad[i].size(); ++j) {
            cout<<ad[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}