#include<bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
vector<int>v[100001];
queue<int>q;
bool viz[100001];
int t[100001];
int cost[1001][1001];
bool bl[1001][1001];
int flow[1001][1001],f,tot;
vector<int>w;
void adauga(int nod)
{
    if(nod==1)
        w.push_back(1);
    else
    {
        adauga(t[nod]);
        w.push_back(nod);
    }
}
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        v[a].push_back(b);
        v[b].push_back(a);
        cost[a][b]=c;
        bl[b][a]=true;
    }
    q.push(1);
    viz[1]=true;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        for(auto x:v[nod])
            if(!viz[x]&&!bl[nod][x])
            {
                t[x]=nod;
                q.push(x);
                viz[x]=true;
            }
    }
    while(viz[n])
    {
        adauga(n);
        for(auto q:w)
            cout<<q<<" ";
        cout<<endl;
        fill(viz,viz+1001,0);
        int cmin=1000001;
        for(int i=0;i+1<w.size();i++)
        {
            int a=w[i];
            int b=w[i+1];
            if(!cost[a][b])
            {
                if(cmin>flow[b][a])
                    cmin=flow[b][a];
            }
            else if(cmin>cost[a][b]-flow[a][b])
                cmin=cost[a][b]-flow[a][b];
        }
        for(int i=0;i+1<w.size();i++)
        {
            int a=w[i];
            int b=w[i+1];
            if(cost[a][b])
                flow[a][b]+=cmin;
            else flow[b][a]-=cmin;
            if(flow[a][b]==cost[a][b])
                bl[a][b]=true;
            if(flow[b][a]==cost[b][a])
                bl[b][a]=true;
        }
        tot+=cmin;
        q.push(1);
        viz[1]=true;
        while(!q.empty())
        {
            int nod=q.front();
            q.pop();
            for(auto x:v[nod])
                if(!viz[x]&&!bl[nod][x])
                {
                    t[x]=nod;
                    q.push(x);
                    viz[x]=true;
                }
        }
        w.clear();
    }
    fout<<tot;
}