#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int Nmax = 1010;
const int Mmax = 5010;

ifstream F("maxflow.in");
ofstream G("maxflow.out");

#define IT(type) vector<type>::iterator

int N,M,total_flow;
vector<int> V[Nmax];

int capacity[Nmax][Nmax];
int last[Nmax],Cmin[Nmax];

int find_paths(int source,int target)
{
    queue<int> Q;
    memset(last,0,sizeof(last));

    last[source] = -1;
    Q.push( source );

    while ( Q.size() )
    {
        int node = Q.front();
        Q.pop();

        for (IT(int) where=V[node].begin();where!=V[node].end();++where)
            if ( capacity[node][*where] > 0 && last[*where] == 0 )
            {
                last[*where] = node;
                Q.push( *where );
            }
    }

    if ( last[target] != 0 )
        return 1;
    return 0;
}

int main()
{
    F>>N>>M;
    for (int i=1,x,y,c;i<=N;++i)
    {
        F>>x>>y>>c;
        if ( capacity[x][y] == 0 && capacity[y][x] == 0 )
        {
            V[ x ].push_back( y );
            V[ y ].push_back( x );
        }
        capacity[x][y] += c;
    }

    int source = 1;
    int target = N;

    while ( find_paths(source,target) != 0 )
    {
        for (IT(int) leaf=V[target].begin();leaf!=V[target].end();++leaf)
        {
            Cmin[*leaf] = capacity[last[*leaf]][*leaf];
            int edges = 0;
            for (int now=*leaf;now!=source;now=last[now])
            {
                Cmin[*leaf] = min( Cmin[*leaf] , capacity[last[now]][now] );
                edges++;
            }
            total_flow += edges * Cmin[*leaf];
        }

        for (IT(int) leaf=V[target].begin();leaf!=V[target].end();++leaf)
            for (int now=*leaf;now!=source;now=last[now])
            {
                capacity[last[now]][now] -= Cmin[*leaf];
                capacity[now][last[now]] += Cmin[*leaf];
            }
    }

    G<<total_flow<<'\n';
}