#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

class graf {

protected:
    int noduri, muchii;
    vector < vector < int >> adiacenta;

public:
    // Constructor cu matrice de adiacenta data
    graf(vector < vector < int >> listaAdiacenta, int noduri, int muchii): adiacenta(listaAdiacenta), noduri(noduri), muchii(muchii) {};

    // Constructor fara matrice de adiacenta, se cu initalizeaza una goala
    graf(int noduri, int muchii): adiacenta(noduri + 1), noduri(noduri), muchii(muchii) {};

    vector < int > bfs(int);
    int dfs();

};

class graf_orientat : public graf{
private:
    void dfsCtc(int, vector < int >&, vector < int >&, stack < int >&, int&, vector < string >&, unordered_set < int >&);
    void dfsSortaret(int, vector < int >&, vector < int >&);

public:
    graf_orientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf(listaAdiacenta, noduri, muchii) {};
    graf_orientat(int noduri, int muchii): graf(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_orientat&);

    vector < string > ctc();

    vector < int > sortaret();
};

class retea : public graf_orientat {
    // Matrice de adianceta care contine si costurile
    vector< vector< pair< int, int >>> adiacentap;
    vector<vector<int>> cost;
    bool auxbfs(int start, int finish, vector<int>& parents, vector<vector<int>> matrix, vector<vector<int>> cost);
public:
    retea(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf_orientat(listaAdiacenta, noduri, muchii) {};
    retea(int noduri, int muchii): adiacentap(noduri+1), graf_orientat(noduri, muchii) {};

    friend istream& operator>>(istream&, retea&);

    int maxflow();

};

istream& operator>>(istream& in, retea& g) {
    g.cost.resize(g.noduri + 1, vector<int>(g.noduri + 1));
    for (int i = 0; i < g.muchii; i++) {
        int aux1, aux2, aux3;
        in >> aux1 >> aux2 >> aux3;
        g.cost[aux1][aux2] = aux3;
        g.adiacenta[aux1].push_back(aux2);
        g.adiacenta[aux2].push_back(aux1);
    }
    return in;
}

bool retea :: auxbfs(int start, int finish, vector<int>& parents, vector<vector<int>> matrix, vector<vector<int>> cost){
    //vector < int > vis(noduri + 1);
    parents.assign(noduri+1, 0);
    queue < int > q;
    q.push(start);
    parents[start] = 1;

    // Se baga pe rand in queue toate nodurile nevizitate ale nodului din capul queue-ului, si se noteaza timpul la care se ajunge la ele
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (int i: adiacenta[curr]){
            if (!parents[i] && cost[curr][i] > matrix[curr][i]) {
                parents[i] = curr;
                if (i != finish){
                    q.push(i);
                }
            }
        }
    }
    return parents[noduri];
}

int retea :: maxflow(){
    vector<int> parents(noduri + 1);
    vector<vector<int>> matrix(noduri + 1, vector<int>(noduri + 1));

    int m = 0, start = 1, finish = noduri, currm = INT_MAX;

    while(this->auxbfs(start, finish, parents, matrix, cost)){
        for(auto p : adiacenta[noduri]){
            if(cost[p][noduri] > matrix[p][noduri] && parents[p]){
                parents[noduri] = p;
                currm = INT_MAX;
                int i = finish, j;
                for(int i = noduri; i != 1; i = parents[i]){
                    j = parents[i];
                    currm = min(currm, abs(cost[j][i] - matrix[j][i]));
                }
                i = finish;
                for(int i = noduri; i != 1; i = parents[i]){
                    j = parents[i];
                    matrix[j][i] += currm;
                    matrix[i][j] -= currm;
                }
                m += currm;
            }
        }
    }
    return m;
}

void maxflowDriver() {
    // https://infoarena.ro/problema/maxflow
    // Citire
    ifstream in ("maxflow.in");
    ofstream out("maxflow.out");

    int n, m;
    in >> n >> m;

    retea x(n, m);
    in >> x;

    out << x.maxflow();

}

int main() {
    // Se apeleaza functia corespunzatoare problemei
    maxflowDriver();
    return 0;
}