# include <stdio.h>
# include <algorithm>
# include <vector>

using namespace std;

# define FIN "critice.in"
# define FOUT "critice.out"
# define MAXN 1010
# define uc unsigned char
# define min(a,b) (a < b ? a : b)

int N,M,a,b,c;
vector <int> list[MAXN];
vector <int> ordi[MAXN];
int cap[MAXN][MAXN];
int flux[MAXN][MAXN];
int pred[MAXN];
int coada[MAXN];
uc s[MAXN];


    int bfs()
    {
        int i,aux,f,l,len;
        f = 0;
        l = 1;
        coada[f] = 1;
        s[1] = 1;
        while (f < l)
          {
              aux = coada[f++];
              len = list[aux].size();
              for (i = 0; i < len; ++i)
               if (s[list[aux][i]] == 0)
                {
                  if (cap[aux][list[aux][i]]>flux[aux][list[aux][i]])
                    {
                        pred[list[aux][i]] = aux;
                        coada[l] = list[aux][i];
                        s[coada[l++]] = 1;
                    }
                else
                  if (flux[list[aux][i]][aux]!=0)
                    {
                        pred[list[aux][i]] = -aux;
                        coada[l] = list[aux][i];
                        s[coada[l++]] = 1;
                    }
                  if (s[N] == 1) return 1;
                }
          } 
        return 0;
    }   

    void flow()
    {
        int aux,a,b,i;
         
        while (bfs()==1)
          {
              aux = N;
              a = 10000;
              b = 10000;
              while (aux != 1)
                {
                  if (pred[aux] < 0) a=min(a,flux[-pred[aux]][aux]);
                   else b=min(b,cap[pred[aux]][aux]-flux[pred[aux]][aux]);
                  aux = pred[aux];
                }
              a = min(a,b);
              aux = N;
              while (aux != 1)
                {
                  if (pred[aux] < 0) flux[-pred[aux]][aux]-=a;
                    else flux[pred[aux]][aux]+=a;
                  aux = pred[aux]; 
                }
              for (i = 1; i <= N; ++i)
                s[i] = 0;
          }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d%d",&N,&M);
        
        int i;
        for (i = 1; i <= M; ++i)
          {
               scanf("%d%d%d",&a,&b,&c);
               if (a==1 || b==N) 
                 {
                    list[a].push_back(b);
                    cap[a][b] = c;
                    ordi[a].push_back(i);
                 } else
               if (b==1 || a==N)
                 {
                    list[b].push_back(a);
                    cap[b][a] = c;
                    ordi[b].push_back(i);
                 } else
               {
                   list[a].push_back(b);
                   list[b].push_back(a);
                   cap[a][b] = cap[b][a] = c;
                   ordi[a].push_back(i);
                   ordi[b].push_back(i);
               }
          }
        flow();  
        
        return 0;          
    }