// VARIANTA 2
// pct a

// Edmonds Karp
// O(nm^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 la 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;           //initializeaza_flux_nul

    }

    S = 1;
    T = n;

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

    g << sol_flux;

    return 0;
}


// pct b
// afișați tăietura minima între sursa și orice alt vârf, adică o mulțime de arce cu costul total minim pe care dacă le eliminăm din rețea
// cel puțin un vârf care era accesibil inițial din sursă după eliminare nu mai este accesibil.

//
//#include <bits/stdc++.h>
//#define N 1005
//using namespace std;
//
//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()
//{
//    cin >> n >> m; /// noduri si muchii
//    for(int i = 0; i < m; i++)
//    {
//        int nod1, nod2, c;
//        cin >> 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();
//    }
//
////    cout << sol_flux;

//    // fac BFS pt a vedea elementele din X
//
//    int vecin;
//    vector<int> bfs;
//    for(int i=0; i<=n; i++)
//    {
//        tata[i] = 0;
//        viz[i] = 0;
//    }
//
//    while(c.empty() == 0)
//        c.pop();
//
//    c.push(S);
//    bfs.push_back(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);
//                bfs.push_back(vecin);
//                viz[vecin] = 1;
//                tata[vecin] = nod;
//            }
//
//    }
//
//    cout<<"X= ";                          // afisare taietura
//    for(int i=0;i<bfs.size();i++)
//        cout<<bfs[i]<<" ";
//    cout<<endl;
//    cout<<"Y= ";
//    for(int i=1;i<=n;i++)
//        for(int j=0;j<bfs.size();j++)
//            if( i != bfs[j] )
//                cout<<i<<" ";
//    return 0;
//}


// 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;
//}
//
//