#include <iostream>
#include <vector>

#define MAX_POW 16
using namespace std;

const int MAXN = 2000;
const int MAXM = 10000;
const int NIL = -1;
const int INF = 2e9;

struct info{
    int to, id;
};

vector <info> adj[MAXN];
int viz[MAXN];
info prevv[MAXN];
int edgesCap[MAXM * 2];
int edgesCapSize;
int flowSize;
int source, destination;
long long p, flux;

int q[MAXN];
int pq, uq;

bool bfs(){
    int u;

    for( u = 0; u < flowSize; u++ ) {
        prevv[u].to = source;
        prevv[u].id = 0;
        viz[u] = false;
    }

    q[0] = source;
    prevv[source].to = NIL;
    viz[source] = true;

    pq = 0;
    uq = 1;
    while( pq < uq && q[pq] != destination ){
        u = q[pq++];

        for( info v : adj[u] ){
            if( !viz[v.to] && edgesCap[v.id] && edgesCap[v.id] >= ((long long) 1 << p) ) {
                viz[v.to] = true;
                prevv[v.to].to = u;
                prevv[v.to].id = v.id;
                q[uq++] = v.to;
            }
        }
    }

    return viz[destination];
}

long long makeFlux() {
    int delta, a;

    while( bfs() ){
        for( info aux : adj[destination] ) {
            prevv[destination].to = aux.to;
            prevv[destination].id = aux.id ^ 1;

            delta = +INF;
            for( a = destination; a != source; a = prevv[a].to ) {
                delta = min(delta, edgesCap[prevv[a].id]);
            }

            flux += delta;

            for( a = destination; a != source; a = prevv[a].to ) {
                edgesCap[prevv[a].id] -= delta;
                edgesCap[prevv[a].id ^ 1] += delta;
            }
        }
    }

    return flux;
}

void addEdge(int a, int b, int cap) {
    adj[a].push_back({b, edgesCapSize});
    edgesCap[edgesCapSize] = cap;
    edgesCapSize++;
    adj[b].push_back({a, edgesCapSize});
    edgesCap[edgesCapSize] = 0;
    edgesCapSize++;
}

void reset() {
    int i;

    for ( i = 0; i < flowSize; i++ ) {
        adj[i].clear();
        viz[i] = false;
        prevv[i].to = prevv[i].id = 0;
    }

    for ( i = 0; i < edgesCapSize; i++ ) {
        edgesCap[i] = 0;
    }
}

int main(){
    FILE *fin, *fout;
    fin = fopen("maxflow.in", "r");
    fout = fopen("maxflow.out", "w");

    int m, i, a, b, aux;

    fscanf(fin, "%d%d", &flowSize, &m);

    flowSize += 10;

    edgesCapSize = 2;
    source = flowSize - 2;
    destination = flowSize - 1;
    for( i = 0; i < m; i++ ) {
        fscanf(fin, "%d%d%d", &a, &b, &aux);
        a--;
        b--;

        if ( a == 0 ) {
            a = flowSize - 2;
        }

        if ( b == flowSize - 11 ) {
            b = flowSize - 1;
        }

        addEdge(a, b, aux);
    }

    flux = 0;
    p = MAX_POW;
    while ( p >= 0 ) {
        makeFlux();
        p--;
    }

    fprintf(fout, "%lld\n", flux);

    fclose(fin);
    fclose(fout);

    return 0;
}