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

#define lmax 1005
#define inf 20000000

using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

queue <int>q;

vector <int>v[lmax];

vector <int>::iterator it;

int n,m,x,y,z,i,j,minim;

long long flux;

int tata[lmax];

int d[lmax][lmax],fl[lmax][lmax];

inline bool bf()
{
    int nod;

    bool ok[lmax];

    for (i=1;i<=n;i++)
     ok[i]=0;

    while (q.size())
     q.pop();

    q.push(1);
    ok[1]=1;

    while (!q.empty() && ok[n]==0)
     {
         nod=q.front();

         q.pop();

         for (it=v[nod].begin();it<v[nod].end();it++)
          if (ok[*it]==0 && d[nod][*it]>fl[nod][*it])
           {
               ok[*it]=1;
               tata[*it]=nod;
               q.push(*it);
           }

     }

    return ok[n];
}

int main()
{

   f>>n>>m;

   for (i=1;i<=m;i++)
    {
        f>>x>>y>>z;

        d[x][y]+=z;
        v[x].push_back(y);
        v[y].push_back(x);
    }

   while (bf())
    {

    for (it=v[n].begin();it<v[n].end();it++)
      if (d[*it][n]>fl[*it][n])
      {
          minim=inf;

          tata[n]=*it;
          j=n;

        while (j)
          {
              if (tata[j] && d[tata[j]][j]-fl[tata[j]][j]<minim)
                minim=d[tata[j]][j]-fl[tata[j]][j];

              j=tata[j];

              cout<<j<<'\n';

          }

        j=n;

         while (j)
          {
              fl[tata[j]][j]+=minim;
              fl[j][tata[j]]-=minim;

              j=tata[j];
              //cout<<9<<" ";
          }

         flux+=minim;
       }
    }

    g<<flux;

   f.close();
   g.close();
}