#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#define INFINIT 9999999
using namespace std;

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

bool vizitat[1001];

//Functia de citire_date returneaza lista de adiacenta a retelei(grafului) iar in acelasi timp rezolva
//prima cerinta a exercitiului, verifica daca fluxul introdus respecta conditiile retelei
list <int>* citire_date(int &n, int **&capacitate, int &sursa, int &destinatie)
{
    int m;
   // f>>n>>sursa>>destinatie>>m;
    f>>n>>m;
    //Se vor folosi doua siruri de numere, fiecare element x al sirului va fi fie fluxul care intra in
    //nodul cu numarul de ordin x, fie fluxul care iese din nodul cu numarul de ordin x
    int *flux_intern= new int [n+1];
    int *flux_extern= new int [n+1];

    for(int i=1;i<=n;++i)
    flux_intern[i]=flux_extern[i]=0;

    capacitate=new int*[n+1];   //Matricea capacitate va retine capacitatea fiecarei muchii din retea
    for(int i=1;i<=n;++i)
    {
        capacitate[i]=new int[n+1];
        for(int j=1;j<=n;++j)
        capacitate[i][j]=0;
    }

    bool corect=true;   //Variabila folosita pentru a verifica corectitudinea fluxului introdus
    list <int> *local_list=new list <int> [n+1];

    for(int i=1;i<=m;++i)
    {
        int x,y,c,h;
            //f>>x>>y>>c>>h;

        f>>x>>y>>c;
        local_list[x].push_back(y);
        local_list[y].push_back(x);

       // if(h>c) {g<<"NU\n";corect=false;}    //Daca am gasit o valoarea a fluxului transmis pe muchia x->y,
                                //atunci fluxul introdus nu este corect
        capacitate[x][y]+=c;
        //flux_extern[x]+=h;  //Actualizez valoarea fluxului care iese din nodul x
       // flux_intern[y]+=h;  //Actualizez valoarea fluxului care intra in nodul y
    }

    //Se verifica fiecare nod, excluzand nodurile statie si destinatie, daca respecta conditia:
    //Valoarea fluxului care intra in nod este egala cu valoarea fluxului care iese din nod
    /*if(corect==true)
    for(int i=1;i<=n;++i)
    if(flux_intern[i]!=flux_extern[i]&&i!=sursa&&i!=destinatie)
    {
        corect=false;
        g<<"NU"<<"\n";
    }    //Daca un nod nu respecta conditia, atunci fluxul introdus nu este corect

    if(corect==true)
    g<<"DA\n";*/
    return local_list;
}

int bfs(int n,list <int> *l, int sursa, int destinatie, int **&capacitate, int *&father, int **&flux)
{
    for(int i=1;i<=n;++i)
    vizitat[i]=0;
    vizitat[sursa]=1;
    queue <int> q;
    q.push(sursa);

    while(!q.empty())
    {
        int nod;
        nod =q.front();

        for(list <int>:: iterator it=l[nod].begin();it!=l[nod].end();++it)
        {if(vizitat[*it]||capacitate[nod][*it]==flux[nod][*it]) continue;

            father[*it]=nod;
            q.push(*it);
            vizitat[*it]=1;
            if(*it==destinatie) return 1;
        }
        q.pop();
    }

    return 0;
}
void flux_maxim(int n,list <int> *l,int sursa,int destinatie, int **capacitate)
{
    int *father=new int[n+1];

    for(int i=1;i<=n;++i)
    father[i]=0;

    int **matrice_flux=new int*[n+1];
    for(int i=1;i<=n;++i) matrice_flux[i]=new int [n+1];
     for(int i=1;i<=n;++i)
     for(int j=1;j<=n;++j)
        {
            matrice_flux[i][j]=0;
        }

    int fluxul=0;
    //cout<<bfs(n,l,sursa,destinatie,capacitate,father,matrice_flux);
    //for(int i=1;i<=n;++i) cout<<father[i]<<" ";
    while(bfs(n,l,sursa,destinatie,capacitate,father,matrice_flux)==1)
    {
        int minimul=INFINIT;
        int nod=destinatie;
        while(father[nod]!=0)
        {
            minimul=min(minimul,capacitate[father[nod]][nod]-matrice_flux[father[nod]][nod]);
            nod=father[nod];
        }
        nod=destinatie;
        while(father[nod]!=0)
        {
            matrice_flux[father[nod]][nod]+=minimul;
            matrice_flux[nod][father[nod]]-=minimul;
            nod=father[nod];
        }
        fluxul+=minimul;
    }

    g<<fluxul;
}
int main()
{
    int sursa, destinatie;
    int n,**capacitate=new int*[0];
    capacitate[0]=new int[0];
    list <int> *l=citire_date(n,capacitate,sursa,destinatie);

    flux_maxim(n,l,1,n,capacitate);
    return 0;
}