#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
int N[1001][1001]; // capacitati
int F[1001][1001]; // flux
int GR[1001][1001];
int n, s, t, m;
ifstream in("maxflow.in");
ofstream out("maxflow.out");
int viz[1001], pred[1001];
bool BFS(){
    for(int i=0;i<=n;i++)
        viz[i] = pred[i] = 0;
    queue<int> Q;
    Q.push(s);
    viz[s] = 1;
    while(!Q.empty()){
        int K = Q.front();
        Q.pop();
        for(int j=1;j<=n;j++){
            if(!viz[j] && GR[K][j] > 0){
                viz[j] = 1;
                pred[j] = K;
                Q.push(j);
                if(j==t) return true;
            }

        }
    }
    return false;
}
int main()
{
    in >> n >> m;
    s = 1; t = n;
    for(int i=1; i<=m; i++)
    {
        int x, y, c, f;
        in >> x >> y >> c;
        f = 0;

        N[x][y] = c;
        F[x][y] = f;
        GR[x][y] = c-f;
        GR[y][x] = f;
    }
    for(int i=1; i<=n;i++){
        if(i!=s && i!=t){
            int s1, s2;
            s1=s2=0;
            for(int j=1;j<=n;j++){
                s1+=F[i][j];
                s2+=F[j][i];
            }
        }
    }

    int x, ip;
    while(BFS()){
        x = t, ip = 1000;
        while(x!=s){
            if(ip > GR[pred[x]][x])
                ip = GR[pred[x]][x];
            x = pred[x];
        }
        x = t;
        while(x!=s){
            if(N[pred[x]][x]){
                F[pred[x]][x] += ip;
                GR[pred[x]][x] -= ip;
                GR[x][pred[x]] += ip;
            } else {
                F[x][pred[x]] -= ip;
                GR[x][pred[x]] += ip;
                GR[pred[x]][x] -= ip;
            }
            x = pred[x];
        }
    }
    // Am calculat ip ( capacitatea reziduala)
    long long sum = 0;
    for(int i=1;i<=n;i++)
        sum+=F[1][i];
    out << sum;
    return 0;
}
// Fie K = (X,Y). K s.n. taietura daca X reunit Y = V ; X inter. Y = 0
// C[K] = capacitatea taieturii
// C[K = (X,Y)] = sum(C(a,b)) CU a din X, b din Y, ab din E