#include<fstream>
#include<vector>
#include<cstring>

using namespace std;

ifstream fin( "maxflow.in" ); ofstream fout( "maxflow.out" );

const int nmax = 1000;
int n;
int start, dest;
bool f[ nmax + 1 ];
int ant[ nmax + 1 ], q[ nmax + 1 ];
int shp[ nmax + 1 ];
int c[ nmax + 1 ][ nmax + 1 ];

vector< int > g[ nmax + 1 ];

bool bfs() {
    int first, last;

    memset( f, 0, sizeof( f ) );
    memset( ant, 0, sizeof( ant ) );

    first = last = 0;
    q[ 0 ] = start;
    f[ start ] = 1;
    while ( first <= last && f[ dest ] == 0 ) {
        int x = q[ first ++ ];
        for( vector< int >::iterator it = g[ x ].begin(); it != g[ x ].end(); ++ it ) {
            if ( f[ *it ] == 0 && c[ x ][ *it ] ) {
                q[ ++ last ] = *it;
                f[ *it ] = 1;
                ant[ *it ] = x;
            }
        }
    }
    return f[ dest ];
}
inline int min2( int a, int b ) {
    return ( a < b ? a : b );
}
int main() {
    int m;
    fin >> n >> m;
    start = 1; dest = n;
    for( int i = 0; i < m; ++ i ) {
        int x, y, z;
        fin >> x >> y >> z;
        g[ x ].push_back( y ); g[ y ].push_back( x );
        c[ x ][ y ] += z;

        if ( x == n ) {
            shp[ y ] += z;
        } else if ( y == n ) {
            shp[ x ] += z;
        }
    }
    while ( bfs() ) {
        for( vector< int >::iterator it = g[ dest ].begin(); it != g[ dest ].end(); ++ it ) {
            if ( f[ *it ] == 1 && c[ *it ][ dest ] ) {
                int tata, k = *it;
                int sol = c[ *it ][ dest ];

                while ( (tata = ant[ k ]) ) {
                    sol = min2( sol, c[ tata ][ k ] );
                    k = tata;
                }

                c[ *it ][ dest ] -= sol;
                c[ dest ][ *it ] += sol;
                k = *it;
                while ( (tata = ant[ k ]) ) {
                    c[ tata ][ k ] -= sol;
                    c[ k ][ tata ] += sol;
                    k = tata;
                }
            }
        }
    }

    int flow = 0;
    for( vector< int >::iterator it = g[ dest ].begin(); it != g[ dest ].end(); ++ it ) {
        flow += (shp[ *it ] - c[ *it ][ n ]);
    }
    fout << flow << "\n";

    fin.close();
    fout.close();
    return 0;
}