/// time = 0.12
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Graph {
  public:
    static const int NIL = -1;
    static const int oo = 0x3f3f3f3f;

    class Edge {
      public:
        int from, to, capacity, flow;

        Edge(const int _from = NIL, const int _to = NIL, const int _capacity = 0):
          from(_from),
          to(_to),
          capacity(_capacity),
          flow(0) {}

        bool IsSaturated() const {
            return capacity == flow;
        }
    };

    Graph(const int _V = 0):
      V(_V),
      E(0),
      edges(vector<Edge>()),
      G(vector< vector<int> >(_V, vector<int>())) {}

    int Size() const {
        return V;
    }

    void AddEdge(const Edge &e) {
        edges.push_back(e);
        G[e.from].push_back(E++);
    }

    int MaximumFlow(const int source, const int sink) {
        InitializeNetwork();
        int maxFlow = 0;
        vector<int> father;
        while (BFS(source, sink, father)) {
            for (vector<int>::const_iterator e = G[sink].begin(); e != G[sink].end(); ++e) {
                if (edges[NonE(*e)].IsSaturated() || father[edges[*e].to] == NIL)
                    continue;
                father[sink] = NonE(*e);
                int flow = oo;
                for (int x = sink; x != source; x = edges[father[x]].from)
                    flow = min(flow, edges[father[x]].capacity - edges[father[x]].flow);
                for (int x = sink; x != source; x = edges[father[x]].from) {
                    edges[father[x]].flow += flow;
                    edges[NonE(father[x])].flow -= flow;
                }
                maxFlow += flow;
            }
        }
        ClearResidualNetwork();
        return maxFlow;
    }

  private:
    int V, E;
    vector<Edge> edges;
    vector< vector<int> > G;

    int NonE(const int e) const {
        if (e < E)
            return e + E;
        else
            return e - E;
    }

    void InitializeNetwork() {
        for (int e = 0; e < E; ++e) {
            edges[e].flow = 0;
            edges.push_back(Edge(edges[e].to, edges[e].from, 0));
            G[edges[e].to].push_back(NonE(e));
        }
    }

    bool BFS(const int source, const int destination, vector<int> &father) const {
        father = vector<int>(V, NIL);
        father[source] = 2 * E;
        queue<int> q;
        for (q.push(source); !q.empty(); q.pop()) {
            int x = q.front();
            if (x == destination)
                continue;
            for (vector<int>::const_iterator e = G[x].begin(); e != G[x].end(); ++e) {
                if (!edges[*e].IsSaturated() && father[edges[*e].to] == NIL) {
                    father[edges[*e].to] = *e;
                    q.push(edges[*e].to);
                }
            }
        }
        return father[destination] != NIL;
    }

    void ClearResidualNetwork() {
        for (; int(edges.size()) > E; edges.pop_back())
            G[edges.back().from].pop_back();
    }
};

Graph G;
int Answer;

void Solve() {
    Answer = G.MaximumFlow(0, G.Size() - 1);
}

void Read() {
    ifstream cin("maxflow.in");
    int v, e;
    cin >> v >> e;
    G = Graph(v);
    for (; e > 0; --e) {
        int x, y, c;
        cin >> x >> y >> c;
        G.AddEdge(Graph::Edge(x - 1, y - 1, c));
    }
    cin.close();
}

void Print() {
    ofstream cout("maxflow.out");
    cout << Answer << "\n";
    cout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}

/*
/// implimentare Emanuela Cherchez
/// tle pe testele 8, 9, 10
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define NMAX 1024
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f

int C[NMAX][NMAX];
int F[NMAX][NMAX];
int TT[NMAX];
vector<int> G[NMAX];
int N, M;
int q[NMAX];
int viz[NMAX];

int BF()
{
    int incq, sfq, nod, j, V;

    memset(viz, 0, sizeof(viz));
    viz[1] = 1;
    incq = sfq = 0;
    q[sfq++] = 1;
    for ( ; incq < sfq and !viz[N]; )
    {
        nod = q[incq++];
        int d = G[nod].size();
        for (j = 0; j < d; j++)
            {
                V = G[nod][j];
                if (!viz[V]) {
                    if (F[nod][V]<C[nod][V])
                    {
                        viz[V] = nod;
                        q[sfq++] = V;
                    }
                    else
                    if (F[V][nod]>0)
                    {
                        viz[V] = -nod;
                        q[sfq++] = V;

                    }
                }
            }
    }

    return ( !viz[N] );
}

inline int abs(int x)
{
    if (x<0) return(-x);
    return (x);
}

void ek()
{
    int i, a, b, lg, v;
    int L[NMAX];
    do {
        if (BF()) return;
        L[0] = N; lg = 0;
        a = b = INF;
        while (L[lg] != 1 )
        {
            ++lg;
            L[lg]=abs(viz[L[lg-1]]);
            if (viz[L[lg-1]]>0)
               a=min(a,C[L[lg]][L[lg-1]]-F[L[lg]][L[lg-1]]);
            else
            if (viz[L[lg-1]]<0)
               b=min(a,F[L[lg-1]][L[lg]]);
        }
        v = min(a,b);
        for (i = lg; i > 0; --i)
           if (viz[L[i-1]] > 0)
               F[L[i]][L[i-1]] += v;
           else
               F[L[i-1]][L[i]] -= v;

    } while (1);

}

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

    int i, flow = 0, x, y, z;

    scanf("%d %d ", &N, &M);

    for (i = 1; i <= M; i++)
    {
        scanf("%d %d %d ", &x, &y, &z);
        C[x][y] += z;
        G[x].pb(y);
        G[y].pb(x);
    }

    ek();

    for (i = 1; i <= N; ++i)
        flow += F[i][N];

    printf("%d\n", flow);

    fclose(stdin);
    fclose(stdout);
    return 0;
}
*/

/*
/// tle pe testele 8, 9, 10
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int WHITE = 0, GRAY = 1, BLACK = 2;
const int MAX_NODES = 1024;
const int oo=0x3f3f3f3f;
int n, m; // nr noduri, nr arce
int c[MAX_NODES+1][MAX_NODES+1]; // capacitati
int f[MAX_NODES+1][MAX_NODES+1]; // flux
int color[MAX_NODES+1]; // pentru bfs
int p[MAX_NODES+1]; // predecesor (ptr. drum crestere)
int ic, sc; // inceput coada, sfarsit coada
int q[MAX_NODES+3]; // coada

void drum(int u);
inline void incoada(int u);
inline int dincoada();
int fluxMax(int s, int t);
bool bfs(int s, int t);
inline int minim(int x, int y);
inline int maxim(int x, int y);

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

    int i,j,k,flux,fluxm; // fluxm=flux_maxim
    scanf("%d%d", &n, &m);
    for(k=1;k<=m;k++)
    {
        scanf("%d%d%d", &i, &j, &flux);
        c[i][j]+=flux;
    }

    fluxm=fluxMax(1,n);

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
           printf("%d\t", maxim(f[i][j],0));
        printf("\n");
    }

    printf("%d\n", fluxm);

    fclose(stdin);
    fclose(stdout);
    return 0;
}// main()

int fluxMax(int s, int t)
{
    int i, j, u, mmin, maxf = 0;
    for(i=1; i<=n; i++)
    for(j=1; j<=n; j++) f[i][j]=0;
    // Cat timp exista drum de crestere a fluxului (in graful rezidual),
    // mareste fluxul pe drumul gasit
    while(bfs(s,t))
    {
        // Determina cantitatea cu care se mareste fluxul
        mmin=oo;
        for(u=t; p[u]!=-1; u=p[u]) mmin=minim(mmin,c[p[u]][u]-f[p[u]][u]);
        // Mareste fluxul pe drumul gasit
        for(u=t; p[u]!=-1; u=p[u])
        {
            f[p[u]][u]+=mmin;
            f[u][p[u]]-=mmin; // sau f[u][p[u]]=-f[p[u]][u];
        }
        maxf += mmin;
        ///printf("drum : ");
        ///drum(t);
        ///printf("\n min = %d maxf = %d\n" , mmin, maxf);
}//     while(...)
//      Nu mai exista drum de crestere a fluxului ==> Gata !!!
        ///printf("\nNu mai exista drum de crestere a fluxului !!!");
    return maxf;
}// fluxMax(...)

bool bfs(int s, int t) // s=sursa t=destinatie
{
// System.out.println("bfs "+s+" "+t+" flux curent :");
// afism(f);
   int u, v;
   bool gasitt=false;
   for(u=1; u<=n; u++) { color[u]=WHITE; p[u]=-1; }
   ic=sc=0; // coada vida
   incoada(s);
   p[s]=-1;
   while(ic!=sc)
   {
       u=dincoada();
       // Cauta nodurile albe v adiacente cu nodul u si pune v in coada
       // cand capacitatea reziduala a arcului (u,v) este pozitiva
      for(v=1; v<=n; v++)
         if(color[v]==WHITE && ((c[u][v]-f[u][v])>0))
         {
             incoada(v);
             p[v]=u;
             if(v==t) { gasitt=true; break;}
         }
      if(gasitt) break;
    }//while

  return gasitt;
}

void drum(int u)
{
   if(p[u]!=-1) drum(p[u]);
   printf("%d ", u);
}// drum(...)

void afism(int a[MAX_NODES][MAX_NODES])
{
    int i,j;
   for(i=1;i<=n;i++)
   {
       for(j=1;j<=n;j++)
       printf("%d\t", a[i][j]);
       printf("\n");
   }
// System.out.println();
}// afism(...)

inline int minim(int x, int y) { return (x<y) ? x : y; }
inline int maxim(int x, int y) { return (x>y) ? x : y; }

inline void incoada(int u)
{
    q[sc++]=u;
    color[u]=GRAY;
}

inline int dincoada()
{
    int u=q[ic++];
    color[u]=BLACK;
    return u;
}
*/
/*
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define NMAX 1024
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f

int C[NMAX][NMAX];
int F[NMAX][NMAX];
int TT[NMAX];
vector<int> G[NMAX];
int N, M;
int cd[NMAX];
int viz[NMAX];

int BF()
{
    int i, j, nod, V;

    cd[0] = 1;
    cd[1] = 1;
    memset(viz, 0, sizeof(viz));
    viz[1] = 1;

    for (i = 1; i <= cd[0]; i++)
    {
        nod = cd[i];
                if (nod == N) continue;
        int d = G[nod].size();
        for (j = 0; j < d; j++)
            {
                V = G[nod][j];
                if (C[nod][V] == F[nod][V] || viz[V]) continue;
                viz[V] = 1;
                cd[ ++cd[0] ] = V;
                TT[V] = nod;
            }
    }

    return viz[N];
}

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

    int i, d, flow, fmin, x, y, z, nod;

    scanf("%d %d ", &N, &M);

    for (i = 1; i <= M; i++)
    {
        scanf("%d %d %d ", &x, &y, &z);
        C[x][y] += z;
        G[x].pb(y);
        G[y].pb(x);
    }

    for (flow = 0; BF();)
        for (i = 0, d = G[N].size(); i < d; i++)
        {
            nod = G[N][i];
            if (F[nod][N] == C[nod][N] || !viz[nod]) continue;
            TT[N] = nod;

            fmin = INF;
            for (nod = N; nod != 1; nod = TT[nod])
                fmin = min(fmin, C[ TT[nod] ][nod] - F[ TT[nod] ][nod]);
            if (fmin == 0) continue;

            for (nod = N; nod != 1; nod = TT[nod])
            {
                F[ TT[nod] ][nod] += fmin;
                F[nod][ TT[nod] ] -= fmin;
            }

            flow += fmin;
        }

    printf("%d\n", flow);

    fclose(stdin);
    fclose(stdout);
    return 0;
}
*/
/*
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define NMAX 1024
#define pb push_back
#define sz size()
#define mp make_pair
#define INF 0x3f3f3f3f

int C[NMAX][NMAX];
int F[NMAX][NMAX];
int TT[NMAX];
vector<int> G[NMAX];
int N, M;
int cd[NMAX];
int viz[NMAX];

int BF()
{
    int i, j, nod, V;

    cd[0] = 1;
    cd[1] = 1;
    memset(viz, 0, sizeof(viz));
    viz[1] = 1;

    for (i = 1; i <= cd[0]; i++)
    {
        nod = cd[i];
        for (j = 0; j < G[nod].sz; j++)
            {
                V = G[nod][j];
                if (C[nod][V] == F[nod][V] || viz[V]) continue;
                viz[V] = 1;
                cd[ ++cd[0] ] = V;
                TT[V] = nod;
                if (V == N) return 1;
            }
    }

    return 0;
}

int main()
{
    freopen("maxflow.in", "rt", stdin);
    freopen("maxflow.out", "wt", stdout);

    int i, flow, fmin, x, y, z, nod;

    scanf("%d %d ", &N, &M);

    for (i = 1; i <= M; i++)
    {
        scanf("%d %d %d ", &x, &y, &z);
        C[x][y] += z;
        G[x].pb(y);
        G[y].pb(x);
    }

    for (flow = 0; BF(); flow += fmin)
    {
        fmin = INF;
        for (nod = N; nod != 1; nod = TT[nod])
            fmin = min(fmin, C[ TT[nod] ][nod] - F[ TT[nod] ][nod]);
        for (nod = N; nod != 1; nod = TT[nod])
        {
            F[ TT[nod] ][nod] += fmin;
            F[nod][ TT[nod] ] -= fmin;
        }
    }

    printf("%d\n", flow);

    fclose(stdin);
    fclose(stdout);
    return 0;
}
*/