#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define DIM 1000

class adj_node{
public:
    int y,cap;
    adj_node(int y, int cap):y{y},cap{cap}{}
};

std::vector<adj_node> G[DIM];
int parent[DIM],taken[DIM];
int n,m,dest,s=0;
bool done=false;

void read(){
    std::ifstream f("maxflow.in");
    f>>n>>m;
    dest=n;
    for(int i=0;i<m;i++){
        int x,y,cap;
        f>>x>>y>>cap;
        bool found=false;
        for(auto node:G[y]) {
            if (node.y == x) {
                found = true;
                break;
            }
        }
        if(found) {
            n++;
            G[x].push_back(adj_node(n, cap));
            G[n].push_back(adj_node(y, cap));
        }
        else
            G[x].push_back(adj_node(y, cap));

    }
    f.close();
}

void init(){
    for(int i=1;i<=n;i++){
        parent[i]=-1;
        taken[i]=0;
    }
}

void BFS(){
    init();
    std::deque<int> q;
    q.push_back(1);
    bool found=false;
    while(!q.empty()){
        int node=q.front();
        q.pop_front();
        for(auto n:G[node]){
            if(taken[n.y]==0){
                taken[n.y]=1;
                parent[n.y]=node;
                q.push_back(n.y);
                if(n.y==dest){
                    found=true;
                    break;
                }
            }
        }
        if(found)
            break;
    }
    if(!found)
        done=true;
}

int find_min(){
    int min=110000,current=dest;
    while(current!=1){
        for(auto n:G[parent[current]]){
            if(n.y==current){
                if(min>n.cap){
                    min=n.cap;
                }
                break;
            }
        }
        current=parent[current];
    }
    return min;
}

void update(int min) {
    int current = dest;
    while (current != 1) {
        for (int i = 0; i < G[parent[current]].size(); i++) {
            if (G[parent[current]][i].y == current) {
                G[parent[current]][i].cap -= min;
                if(G[parent[current]][i].cap==0){
                    G[parent[current]].erase(G[parent[current]].begin()+i);
                }
                bool found=false;
                for(int j=0;j<G[current].size();j++){
                    if(G[current][j].y==parent[current]){
                        found=true;
                        G[current][j].cap+=min;
                        break;
                    }
                }
                if(!found){
                    G[current].push_back(adj_node(parent[current],min));
                }
                break;
            }
        }
        current=parent[current];
    }
}

void print_graph(){
    int i=0;
    for(i=1;i<=n;i++){
        for(auto j:G[i]){
            std::cout<<i<<" "<<j.y<<" "<<j.cap<<"\n";
        }
    }
    std::cout<<"\n\n";
}

void FordFulkerson(){
    while (!done){
        BFS();
        if(!done){
            int min=find_min();
            print_graph();
            update(min);
            print_graph();
        }
    }
    for(auto node:G[dest]){
        s+=node.cap;
    }
}

void print(){
    std::ofstream f("maxflow.out");
    f<<s;
    f.close();
}

int main() {
    read();
    FordFulkerson();
    print();
    return 0;
}