#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

int N1, N2, N3, N4, N5;

class graph
{
public:
    int N, S, D;
    void add_edge (int x, int y, int c)
    {
        X[++M] = x, Y[M] = y, C[M] = c, v[x].push_back (M);
        X[++M] = y, Y[M] = x, C[M] = 0, v[y].push_back (M);
    }

    int max_flow ()
    {
        int ans = 0;
        while (bfs ())
        {
            for (vector < int > :: iterator it = v[D].begin (); it != v[D].end (); it ++)
            if (t[Y[*it]] != -1 && F[opus (*it)] < C[opus (*it)])
            {
                int mini = 1 << 25;
                t[D] = opus (*it);
                for (int i=D; i != S; i = X[t[i]])
                    if (C[t[i]] - F[t[i]] < mini)
                        mini = C[t[i]] - F[t[i]];
                ans += mini;
                for (int i=D; i != S; i = X[t[i]])
                    F[t[i]] += mini, F[opus (t[i])] -= mini;
            }
        }
        return ans;
    }
private:
    int M = 0, t[400009], X[400009], Y[400009], C[400009], F[400009];
    vector < int > v[1509];

    int opus (int M)
    {
        if (M & 1) return M + 1;
        return M - 1;
    }

    bool bfs ()
    {
        queue < int > cc;
        for (int i=1; i<=N; i++)
            t[i] = -1;
        cc.push (S), t[S] = 0;
        while (!cc.empty ())
        {
            int nod = cc.front ();
            cc.pop ();
            for (vector < int > :: iterator it = v[nod].begin (); it != v[nod].end (); it ++)
                if (t[Y[*it]] == -1 && C[*it] > F[*it])
                {
                    cc.push (Y[*it]), t[Y[*it]] = *it;
                    if (Y[*it] == D) return 1;
                }
        }
        return 0;
    }
}net;

void Test ()
{
    int M;
    scanf ("%d %d", &net.N, &M), net.S = 1, net.D = net.N;
    while (M --)
    {
        int x, y, c;
        scanf ("%d %d %d", &x, &y, &c);
        net.add_edge (x, y, c);
    }
    printf ("%d\n", net.max_flow ());
}

int code (int i, int j)
{
    if (i == 1) return j + 1;
    if (i == 2) return N1 + 1 + j;
    if (i == 3) return N1 + N2 + 1 + j;
    if (i == 4) return N1 + N2 + N3 + 1 + j;
    return N1 + N2 + N3 + N4 + 1 + j;
}

int main ()
{
freopen ("maxflow.in", "r", stdin);
freopen ("maxflow.out", "w", stdout);

Test ();

/*scanf ("%d %d %d %d %d", &N2, &N4, &N1, &N3, &N5), net.N = N1 + N2 + N3 + N4 + N5 + 2, net.S = 1, net.D = net.N;
for (int i=1; i<=N1; i++)
    net.add_edge (1, code (1, i), 1);
for (int i=1; i<=N5; i++)
    net.add_edge (code (5, i), net.N, 1);

for (int i=1; i<=N2; i++)
{
    int l, x;
    scanf ("%d", &l);
    while (l --)
        scanf ("%d", &x), net.add_edge (code (1, x), code (2, i), 1);
    scanf ("%d", &l);
    while (l --)
        scanf ("%d", &x), net.add_edge (code (2, i), code (3, x), 1);
}

for (int i=1; i<=N4; i++)
{
    int l, x;
    scanf ("%d", &l);
    while (l --)
        scanf ("%d", &x), net.add_edge (code (3, x), code (4, i), 1);
    scanf ("%d", &l);
    while (l --)
        scanf ("%d", &x), net.add_edge (code (4, i), code (5, x), 1);
}
printf ("%d\n", net.max_flow ());*/

return 0;
}