/*#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>

#define INFL "maxflow.in"
#define OUTFL "maxflow.out"

using namespace std;

#define nmax 1001

int C[nmax][nmax], Cf[nmax][nmax], F[nmax][nmax], e[nmax], h[nmax];
int inq[nmax];
int n, m;

vector<int> LA[nmax];

void read() {
	scanf("%d%d", &n, &m);

	int a, b, c;
	for(int i=1; i<=m; ++i) {
		scanf("%d%d%d", &a, &b, &c);

		LA[a].push_back(b);
		//LA[b].push_back(a);
		C[a][b] = c;
		Cf[a][b] = c;
	}
}

void init_preflow() {
	h[1] = n;
	
	for(int i=0; i<LA[1].size(); ++i) {
		int u = LA[1][i];
		
		F[1][u] = C[1][u];
		F[u][1] = -F[1][u];

		e[u] = C[1][u];
		e[1] -= C[1][u];

		Cf[1][u] = C[1][u] - F[1][u];
		Cf[u][1] = C[u][1] - F[u][1];
	}
}

void push(int u, int v) {
	int flow = min(e[u], Cf[u][v]);

	F[u][v] += flow;
	F[v][u] = -F[u][v];

	e[u] -= flow;
	e[v] += flow;

	Cf[u][v] = C[u][v] - F[u][v];
	Cf[v][u] = C[v][u] - F[v][u];
}

void solve() {
	init_preflow();

	queue<int> q;
	int u, v, mi;

	for(int i=0; i<LA[1].size(); ++i) {
		u = LA[1][i];
		
		if(u != n) {
			q.push(u);
			inq[u] = 1;
		}
	}

	//printf("Here 1\n");

	while(!q.empty()) {
		u = q.front();
		mi = -1;

		//printf("Here 2 - %d %d\n", u, h[u]);

		for(int i=0; i < LA[u].size() && e[u] > 0; ++i) {
			v = LA[u][i];

			if(Cf[u][v] > 0) {
				if(h[u] > h[v]) {
					push(u, v);

					//printf("Push %d %d\n", u, v);

					if(!inq[v] && v != 1 && v != n) {
						inq[v] = 1;
						q.push(v);
					}
				}
				else if(mi == -1) 
					mi = h[v];
				else 
					mi = min(mi, h[v]);
			}
		}

		if(e[u] != 0) 
			h[u] = 1 + mi;
		else {
			inq[u] = 0;
			q.pop();
		}
	}

	printf("%d\n", e[n]);
}

int main() {
//#define ONLINE_JUDGE 1
#ifndef ONLINE_JUDGE
	freopen(INFL, "r", stdin);
	freopen(OUTFL, "w", stdout);
#endif

	read();
	solve();
	
	return 0;
}*/




#include<fstream>
#include<string.h>
#include<vector>
#include<queue>
#define inf "maxflow.in"
#define outf "maxflow.out"
#define NMax 1100
#define MMax 5100
#define INF 0x3f3f3f3f
using namespace std;
 
fstream f(inf,ios::in),g(outf,ios::out);
 
int N,M;
vector<int> LA[NMax];
int C[NMax][NMax],F[NMax][NMax];
int viz[NMax],T[NMax];
 
void read()
{
    f>>N>>M;
    int a,b,c;
    for(int i=1; i<=M; i++)
    {
        f>>a>>b>>c;
        C[a][b] = c;
        LA[a].push_back(b);
        LA[b].push_back(a);
    }
}
 
int BFS()
{
    memset( viz, 0, sizeof(viz) );
 
    viz[1] = 1;
    queue<int> q;
    q.push(1);
 
    while( !q.empty() )
    {
        int x =  q.front(); q.pop();
        if( x==N ) continue;
        for(int i=0; i<LA[x].size(); i++)
        {
            int v = LA[x][i];
            if( C[x][v] == F[x][v] || viz[v] ) continue;
            viz[v] = 1;
            T[v] = x;
            q.push(v);
        }
    }
 
    return viz[N];
}
 
inline int min(int a,int b) { return ( a<b ? a : b ); }
 
void solve()
{
    int flow = 0;
 
    while( BFS() )
    {
        for(int i=0; i<LA[N].size(); i++)
        {
            int nod = LA[N][i];
            if( F[nod][N] == C[nod][N] || !viz[nod] ) continue;
            T[N] = nod;
 
            int fmin = INF;
 
            for( nod = N; nod!=1; nod=T[nod] )
                fmin = min(fmin, C[ T[nod] ][nod] - F[ T[nod] ][nod] );
 
            if( fmin==0 ) continue;
 
            for( nod = N; nod != 1; nod = T[nod] )
            {
                F[ T[nod] ][nod] += fmin;
                F[nod][ T[nod] ] -= fmin;
            }
 
            flow += fmin;
        }
    }
 
    g<< flow;
}
 
int main()
{
    read(); solve();
    f.close(); g.close();
    return 0;
}