// VARIANTA 1
// 70/100

//#include <bits/stdc++.h>
//using namespace std;
//
//ifstream f("maxflow.in");
//ofstream g("maxflow.out");
//
//int capacitate_flux[1001][1001];
//int flowPassed[1001][1001];
//vector<int> graf[1001];
//int parList[1001];
//int currentPathC[1001];
//
//int bfs(int start, int end)//breadth first search
//{
//    memset(parList, -1, sizeof(parList));
//    memset(currentPathC, 0, sizeof(currentPathC));
//    queue<int> q;//declare queue vector
//
//    q.push(start);
//    parList[start] = -1;//initialize parlist’s source node
//    currentPathC[start] = 999;//initialize currentpath’s source node
//
//    while(!q.empty())// if q is not empty
//    {
//        int nod_curent = q.front();
//        q.pop();
//        for(int i=0; i < graf[nod_curent].size(); i++)
//        {
//            int to = graf[nod_curent][i];
//            if(parList[to] == -1)
//            {
//                if(capacitate_flux[nod_curent][to] - flowPassed[nod_curent][to] > 0)
//                {
//                    parList[to] = nod_curent;
//                    currentPathC[to] = min(currentPathC[nod_curent], capacitate_flux[nod_curent][to] - flowPassed[nod_curent][to]);
//                    if(to == end)
//                    {
//                        return currentPathC[end];
//                    }
//                    q.push(to);
//                }
//            }
//        }
//    }
//    return 0;
//}
//
//int edmondsKarp(int start, int end)
//{
//    int maxFlow = 0;
//    while(true)
//    {
//        int flux = bfs(start, end);
//        if (flux == 0)
//        {
//            break;
//        }
//        maxFlow += flux;
//        int nod_curent = end;
//        while(nod_curent != start)
//        {
//            int nod_anterior = parList[nod_curent];
//            flowPassed[nod_anterior][nod_curent] += flux;
//            flowPassed[nod_curent][nod_anterior] -= flux;
//            nod_curent = nod_anterior;
//        }
//    }
//    return maxFlow;
//}
//int main()
//{
//    int N, M;
////    cout<<"enter the number of nodes and edges\n";
//    f >> N >> M;
//    int source=1, dest=N;
//
//    for(int ed = 0; ed < M; ed++)
//    {
////        cout<<"enter the start and end vertex along with capacitate\n";
//        int from, to, cap;
//        f>>from>>to>>cap;
//        capacitate_flux[from][to] = cap;
//        graf[from].push_back(to);
//        graf[to].push_back(from);
//    }
//    int maxFlow = edmondsKarp(source, dest);
//    g<<maxFlow<<endl;
//}
//
//


// VARIANTA 2

#include <bits/stdc++.h>
#define N 1005
using namespace std;

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

int cap[N][N], flux[N][N], viz[N], tata[N];
vector <int> muchii[N]; /// lista de muchii
vector <int> muchii_intoarcere[N]; /// lista de muchii intoarcere
queue<int> c;
int n, m, S, T;
int sol_flux;


int Constr_Lant_Nesat_BF()
{
    int vecin;
    for(int i=0; i<=n; i++)
    {
        tata[i] = 0;
        viz[i] = 0;
    }

    while(c.empty() == 0)
        c.pop();

    c.push(S);
    viz[S] = 1;
    int nod;
    while(c.empty() == 0)
    {

        nod = c.front();
        c.pop();
        for(auto vecin : muchii[nod])
            if(viz[vecin] == 0 && cap[nod][vecin] - flux[nod][vecin] > 0)
            {
                c.push(vecin);
                viz[vecin] = 1;
                tata[vecin] = nod;
                if(vecin == T)
                    return 1;
            }
        /// muchia de intoarcere
        for(auto vecin : muchii_intoarcere[nod])
            if(viz[vecin] == 0 && flux[vecin][nod] > 0)
            {
                c.push(vecin);
                viz[vecin] = 1;
                tata[vecin] = -nod;
                if(vecin == T)
                    return 1;
            }
    }

    return 0;
}

void Reviz_Flux_Lant()
{
    /// plecam in sens invers, de la T -> S

    for(auto vecin : muchii_intoarcere[T])
        if(flux[vecin][T] != cap[vecin][T] && viz[vecin]==1)
        {

            tata[T] = vecin;
            int flux_min = N*N;
            int nod = T;
            while(nod != S) /// cat timp nodul actual nu e nodul de unde am inceput
            {
                int parent = tata[nod];
                if(parent > 0)
                {
                    int dif = cap[parent][nod] - flux[parent][nod];
                    flux_min = min(flux_min, dif);
                }
                else
                {
                    flux_min = min(flux_min, flux[nod][-parent]);
                }
                nod = parent;
                if(nod < 0)
                    nod = (-1) * nod;
            }

            nod = T;
            while(nod != S)
            {
                int parent = tata[nod];
                if(parent > 0)
                    flux[parent][nod] = flux[parent][nod] + flux_min;

                else
                    flux[nod][-parent] = flux[nod][-parent] - flux_min;

                nod = parent;
                if(nod < 0)
                    nod = (-1) * nod;

            }

            sol_flux = sol_flux + flux_min;
        }

}

int main()
{
    f >> n >> m; /// noduri si muchii
    for(int i = 0; i < m; i++)
    {
        int nod1, nod2, c;
        f >> nod1 >> nod2 >> c;
        muchii[nod1].push_back(nod2);
        muchii_intoarcere[nod2].push_back(nod1);
        /// matricea cap tine capacitatea maxima a muchiei nod1-nod2
        cap[nod1][nod2] = c;
        /// matricea flux reprezinta fluxul care trece prin muchia nod1-nod2
        /// care initial e 0
        flux[nod1][nod2] = 0;

    }

    S = 1;
    T = n;

    while(Constr_Lant_Nesat_BF())
    {
        Reviz_Flux_Lant();
    }

    g << sol_flux;

    return 0;
}



// VARIANTA 3

////#include <iostream>
////#include <bits/stdc++.h>
////using namespace std;
//////#define V 100
////
////int N;
////int graph[1001][1001];
////int rGraph[1001][1001];
//////int V;
////
/////* Returns true if there is a path from source 's' to sink 't' in
//// * residual graph. Also fills tata[] to store the path */
////bool BFs( int s, int t, int tata[])
////{
////    // Create a vizitat array and mark all vertices as not vizitat
////    bool vizitat[1001];
////    memset(vizitat, 0, sizeof(vizitat));
////    // Create a queue, enqueue source vertex and mark source vertex
////    // as vizitat
////    queue <int> q;
////    q.push(s);
////    vizitat[s] = true;
////    tata[s] = -1;
////    // Standard BFS Loop
////    while (!q.empty())
////    {
////        int u = q.front();
////        q.pop();
////        for (int v = 0; v < N; v++)
////            if (vizitat[v] == false && rGraph[u][v] > 0)
////            {
////                q.push(v);
////                tata[v] = u;
////                vizitat[v] = true;
////            }
////    }
////    // If we reached sink in BFS starting from source, then return
////    // true, else false
////    return vizitat[t] == true;
////}
////// Returns tne maximum flux from s to t in the given graph
////int fordFulkerson( int s, int t, int N)
////{
////    int u, v;
////    // Create a residual graph and fill the residual graph with
////    // given capacities in the original graph as residual capacities
////    // in residual graph
////    int rGraph[N][N]; // Residual graph where rGraph[i][j] indicates
////    // residual capacitate of edge from i to j (if there
////    // is an edge. If rGraph[i][j] is 0, then there is not)
////    for (u = 0; u < N; u++)
////        for (v = 0; v < N; v++)
////            rGraph[u][v] = graph[u][v];
////    int tata[N];  // This array is filled by BFS and to store path
////    int flux_max = 0;  // There is no flux initially
////    // Augment the flux while tere is path from source to sink
////    while (BFs( s, t, tata))
////    {
////        // Find minimum residual capacitate of the edges along the
////        // path filled by BFS. Or we can say find the maximum flux
////        // through the path found.
////        int path_flow = INT_MAX;
////        for (v = t; v != s; v = tata[v])
////        {
////            u = tata[v];
////            path_flow = min(path_flow, rGraph[u][v]);
////        }
////        // update residual capacities of the edges and reverse edges
////        // along the path
////        for (v = t; v != s; v = tata[v])
////        {
////            u = tata[v];
////            rGraph[u][v] -= path_flow;
////            rGraph[v][u] += path_flow;
////        }
////        // Add path flux to overall flux
////        flux_max += path_flow;
////    }
////    // Return the overall flux
////    return flux_max;
////}
////
////int main(){
////    int M, x, y, z;
////    int Flux_max;
////
////
////    cin>>N>>M;  // noduri, muchii
////    int graf[N][N];
////
////    for(int i=1;i<=N;i++)
////        for(int j=1;j<=N;j++)
////            graf[i][j]=0;
////
////    for(int i=0;i<M;i++){
////        cin>>x>>y>>z;
////        graf[x][y]=z;
////    }
////
////    for(int i=1;i<=N;i++){
////        for(int j=1;j<=N;j++)
////            cout<<graf[i][j]<<" ";
////        cout<<endl;}
////
////    // 1 sursa, N destinatia
////    Flux_max= fordFulkerson(1,N,N);
////    cout<<Flux_max;
////
////}
////