#include <bits/stdc++.h>
#define INF 100000
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int n,m,j,z,x,y,c,q,t[1005],fmn;
int d[1005][1005],f[1005][1005];
vector <int> v[1005];
bool viz[1005];
queue <int>C;
void BFS()
 {int i;
  memset(viz,0,sizeof(viz));
  C.push(1);
  viz[1]=1;
  while(!C.empty())
    {c=C.front();
     C.pop();
     for(i=0;i<v[c].size();i++)
        {q=v[c][i];
         if(viz[q]==0&&d[c][q]!=f[c][q])
           {viz[q]=1;
             if(q!=n){C.push(q);
                     t[q]=c;
                    }
           }
        }
    }
 }
int main()
{int i;
 fin>>n>>m;
 for(i=1;i<=m;i++)
    {fin>>x>>y>>z;
     v[x].push_back(y);
     v[y].push_back(x);
     d[x][y]=z;
    }
    BFS();
 while(viz[n]==1)
      {for(i=0;i<v[n].size();i++)
          {fmn=INF;
           if(viz[v[n][i]]==1&&d[v[n][i]][n]!=f[v[n][i]][n])
           {t[n]=v[n][i];
            q=n;
             while(q!=1)
                   {fmn=min(fmn,d[t[q]][q]-f[t[q]][q]);
                    q=t[q];
                   }

           q=n;
             while(q!=1)
                   {f[t[q]][q]=+fmn;
                    f[q][t[q]]=-fmn;
                    q=t[q];
                   }

           }
          }
       BFS();
     }
}