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

using namespace std;

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

const int NMAX = 2e3 + 100, INF = 2e9;

int N, M, T[NMAX];

long long C[NMAX][NMAX], F[NMAX][NMAX];

vector < int > G[NMAX];

static inline void Add_Edge (int X, int Y, int Z)
{
    C[X][Y] = Z;
    C[Y][Z] = 0;

    F[X][Y] = F[Y][X] = 0;

    G[X].push_back(Y);
    G[Y].push_back(X);

    return;
}

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int X = 0, Y = 0, Z = 0;

        f >> X >> Y >> Z;

        Add_Edge(X, Y, Z);
    }

    return;
}

static inline bool BFS ()
{
    for(int i = 1; i <= N; ++i)
        T[i] = -1;

    T[1] = 0;

    queue < int > Q;

    Q.push(1);

    while(!Q.empty())
    {
        int Node = Q.front();
        Q.pop();

        for(auto it : G[Node])
            if(T[it] == -1 && C[Node][it] != F[Node][it]) /// Muchie "nesaturata";
            {
                T[it] = Node;

                if(it == N)
                    return 1;

                Q.push(it);
            }
    }

    return 0;
}

static inline int Flow ()
{
    int ans = 0;

    while(BFS())
    {
        for(auto it : G[N]) /// Muchiile adiacente destinatiei;
            if(T[it] != -1)
            {
                int Add = C[it][N] - F[it][N];

                int Node = it, Dad = 0;
                while(Node != 1)
                {
                    Dad = T[Node];

                    Add = min(1LL * Add, C[Dad][Node] - F[Dad][Node]);

                    Node = Dad;
                }

                ans += Add;

                F[it][N] += Add;
                F[N][it] -= Add;

                Node = it;
                while(Node != 1)
                {
                    Dad = T[Node];

                    F[Dad][Node] += Add;
                    F[Node][Dad] -= Add;

                    Node = Dad;
                }
            }
    }

    return ans;
}

int main()
{
    Read();

    g << Flow() << '\n';

    return 0;
}