#include <bits/stdc++.h>

using namespace std;

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

bool BFS(vector<vector<int>>&path,vector<vector<int>>&flux,vector<int>&parent,bitset<1005>&viz)
{
    int source=1,dest=path.size()-1,current;
    queue<int>q;
    q.push(source);
    viz[source]=1;
    while(!q.empty())
    {
        current=q.front();
        q.pop();
        for(unsigned i=0;i<path[current].size();i++)
        {
            if(flux[current][path[current][i]]!=0 && viz[path[current][i]]!=1)
            {
                if(path[current][i]==dest)
                {
                    parent[dest]=current;
                    viz[dest]=1;
                    return true;
                }
                q.push(path[current][i]);
                viz[path[current][i]]=1;
                parent[path[current][i]]=current;
            }
        }
    }

    return false;
}

void Update(int &max_flux,vector<vector<int>>&flux,vector<int>&parent,bitset<1005>&viz)
{
    int dest=flux.size()-1;
    int current=dest,par;
    int min_flux=flux[parent[dest]][dest];

    while(current!=1)
    {
        par=parent[current];
        min_flux=min(min_flux,flux[par][current]);
        current=par;

        cout<<current<<' ';
    }

    cout<<'\n';


    current=dest;
    while(current!=1)
    {
        par=parent[current];
        //cout<<flux[par][current]<<' ';
        flux[par][current]-=min_flux;
        //cout<<flux[par][current]<<'\n';
        //cout<<flux[current][par]<<' ';
        flux[current][par]+=min_flux;
        //cout<<flux[current][par]<<'\n';
        current=par;
    }

    cout<<min_flux<<'\n';

    max_flux+=min_flux;

    viz.reset();
    for(unsigned i=0;i<parent.size();i++)
        parent[i]=0;

}

int main()
{
    int n,m;
    fin>>n>>m;
    vector<vector<int>>path(n+1);
    vector<vector<int>>flux(n+1,vector<int>(n+1,0));
    vector<int>parent(n+1);
    bitset<1005>viz;
    int x,y,z;
    for(;m;m--)
    {
        fin>>x>>y>>z;
        path[x].push_back(y);
        path[y].push_back(x);
        flux[x][y]=z;
    }

    int max_flux=0;

    while(BFS(path,flux,parent,viz))
    {
        Update(max_flux,flux,parent,viz);
    }

    fout<<max_flux<<'\n';

    return 0;
}