#include <fstream.h>
//using namespace std;

unsigned long int r[1001][1001];

int n,m,i,a,b;

unsigned long int cost, flux = 0, minim;

int bf[1001], ant[1001], st, dr;

int drum[1001], cont;

int sel[1001];

int main()
{
	ifstream f("maxflow.in");

   f >> n >> m;

   for (i = 1; i <= m; i++)
   {
   	f >> a >> b >> cost;
      r[a][b] = cost;
      r[b][a] = cost;
   }

   f.close();

   int gasit;

   do
   {
   	gasit = 0;
   	//cauta un drum de crestere
      for (i = 1; i <= n; i++)
      	sel[i] = 0;
		sel[1] = 1;

      bf[1] = 1;
      ant[1] = 0;
      st = 0;
      dr = 1;
      do
      {
      	st++;
         if (st <= dr)
         {
         	for (i = 1; i <= n; i++)
        		if (r[bf[st]][i] && !sel[i])
           	 {
           	 	if (i == n)
               		gasit = 1;
            	dr++;
             	bf[dr] = i;
               ant[bf[dr]] = bf[st];
               sel[i] = 1;
             }
         }
      }while(st <= dr);

      //reconstituirea drumului

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

		drum[1] = n;
      cont = 1;

      do
      {
         if(ant[drum[cont]])
         {
         	cont++;
            drum[cont] = ant[drum[cont-1]];
         }
      }while (ant[drum[cont]]);

      //gaseste minimul

      minim = 110001;
		for(i = 1; i < cont; i++)
      	if (r[drum[i]][drum[i+1]] < minim)
         	minim = r[drum[i]][drum[i+1]];

      //scaderea minimului de pe drum

      for (i = 1; i < cont; i++)
      {
      	r[drum[i]][drum[i+1]] -= minim;
         r[drum[i+1]][drum[i]] -= minim;
      }

      flux += minim;
   }while(gasit);

   ofstream g("maxflow.out");
   g << flux << '\n';
   g.close();

   return 0;
}