#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

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

class graph{
    const int INF = (1<<30)-1;
    vector< vector < int > > Ad;
    vector< vector < int > > EdgeValue;
    const int nodes;
    int edges = 0; struct disjoint_set{
        int parent, sz;
    };
    struct edge{
        int x, y, v; bool operator < ( const edge & E ) {
            return v < E.v;
        }
    }; int Find( vector < disjoint_set > & ds, int x);
    void Union(vector < disjoint_set > & ds, int x, int y);
    void DFS_r( int nod, vector < bool > & vis, vector < vector < int > > & ad, vector < int > & comp );
    void DFS_diameter( int nod, int parent, int lg, int& lgmax, int& last );
    void TopoDFS( int nod, vector < bool > & vis, stack < int > & Topo );
    bool BFSflow( int source, int sync, const vector < vector < int > > & AdRes, int** cap, int** flow, int* parent );
public:
    graph( int n):nodes(n){ Ad.resize(nodes+1); }
    graph( int n, int m, vector < vector < int > > & ad ) : nodes(n), edges(m){
        Ad.resize(nodes+1);
        for( int i = 1; i <= nodes; ++i ){
            for( int j = 0; j < ad[i].size(); ++j)
                Ad[i].push_back(ad[i][j]);
        }
    }
    graph( int n, int m, vector < vector < int > > & ad, vector < vector < int > > & values ) : nodes(n), edges(m){
        Ad.resize(nodes+1);
        EdgeValue.resize(nodes+1);
        for( int i = 1; i <= nodes; ++i )
            for( int j = 0; j < ad[i].size(); ++j){
                Ad[i].push_back(ad[i][j]);
                EdgeValue[i].push_back(values[i][j]);
            }
    } int getNodes(){ return nodes; } void addEdge(int x, int y, bool oriented);
    void DFS( int nod, bool vis[] );
    void BFS( int nod );
    int ConnectedComponents();
    void readWeighted();
    void Kruskal();
    void Dijkstra( int nod );
    void BellmanFord( int nod );
    void TopoSort();
    vector < vector < int > > StronglyConnectedComponents();
    int** RoyFloyd();
    int Diameter();
    int MaxFlow( int source, int sync );
};void graph::addEdge(int x, int y, bool oriented){
    Ad[x].push_back( y );
    if( oriented == false )
        Ad[y].push_back(x);
    edges++;
}
void graph::DFS( int nod, bool vis[] ){
    vis[nod] = 1;
    for( int i = 0; i < Ad[nod].size(); ++i ){
        int w = Ad[nod][i];
        if( vis[w] == 0 )DFS(w,vis);
    }
}
void graph::DFS_r( int nod, vector < bool > & vis, vector < vector < int > > & ad, vector < int > & comp ){
    vis[nod] = 1;
    comp.push_back( nod );
    for( int i = 0; i < ad[nod].size(); ++i ){
        int w = ad[nod][i];
        if( vis[w] == 0 )DFS_r(w, vis, ad, comp);
    }
};

void graph::BFS( int nod ){
    queue < int > Q;
    int dist[nodes + 1] = {0};
    Q.push(nod);
    int x; while( !Q.empty() ){
        x = Q.front();
        Q.pop(); for( int i = 0; i < Ad[x].size(); ++i ){
            int w = Ad[x][i]; if( dist[w] == 0 && w != x && w != nod ){
                dist[w] = dist[x] + 1;
                Q.push(w);
            }
        }
    } for( int i = 1; i <= nodes; ++i )
        if( dist[i] != 0 || i == nod )fout << dist[i] << ' ';
        else fout << "-1 ";
}

int graph::ConnectedComponents(){
    int nr = 0;
    bool vis[nodes + 1] = {0};
    for( int i = 1; i <= nodes; ++i )
        if( vis[i] == 0 ){
            DFS(i,vis);
            nr++;
        }
    return nr;
}
int graph::Find( vector < disjoint_set > & ds, int x){ int aux, root = x;
    while( ds[root].parent != root ) root = ds[root].parent;
    while( ds[x].parent != x ){
        aux = ds[x].parent;
        ds[x].parent = root;
        x = aux;
    }
    return root;
}
void graph::Union(vector < disjoint_set > & ds, int x, int y){ int root_x = Find(ds,x);
    int root_y = Find(ds,y); if( ds[root_x].sz >= ds[root_y].sz ){
        ds[root_x].sz += ds[root_y].sz;
        ds[root_y].parent = root_x;
    }
    else{
        ds[root_y].sz += ds[root_x].sz;
        ds[root_x].parent = root_y;
    }
}
void graph::Kruskal(){
    vector < disjoint_set > disjoint_sets;
    vector < edge > E; int M;
    fin >> M;
    int x, y, v; disjoint_sets.resize(nodes+1);
    for( int i = 1; i <= nodes; ++i )
        disjoint_sets[i] = {i,1}; for( int i = 1; i <= M; ++i ){
        fin >> x >> y >> v;
        E.push_back({x,y,v});
    } sort( E.begin(), E.end() ); vector < pair < int , int > > Sol;
    int TotalValue = 0, edges_nr = 0; for( int i = 0; i < M && edges_nr < nodes; ++i ){
        int root_x = Find(disjoint_sets, E[i].x);
        int root_y = Find(disjoint_sets, E[i].y);
        if( root_x != root_y ){
            edges_nr++;
            Sol.push_back( {E[i].x, E[i].y} );
            TotalValue += E[i].v;
            Union(disjoint_sets, root_x, root_y );
        }
    }
    fout << TotalValue << '\n'; fout << Sol.size() << '\n';
    for( int i = 0; i < Sol.size(); ++i )
        fout << Sol[i].first << ' ' << Sol[i].second << '\n';
}
void graph::Dijkstra(int nod){
    priority_queue< pair < int, int >, vector < pair <int, int> >, greater < pair < int, int > > > H;
    vector < int > dist(nodes+1,INF);
    vector < bool > vis(nodes+1, 0);
    dist[nod] = 0;
    H.push( {0,nod} ); while( !H.empty() ){
        nod = H.top().second;
        H.pop(); if( vis[nod] ) continue;
        else vis[nod] = 1; for( int i = 0; i < Ad[nod].size(); ++i ){ int w = Ad[nod][i];
            int dw = EdgeValue[nod][i]; if( dist[w] > dist[nod] + dw ){
                dist[w] = dist[nod] + dw;
                H.push( { dist[w], w } );
            }
        }
    } for( int i = 2; i <= nodes; ++i )
        (dist[i] != INF) ? fout << dist[i] << ' ': fout << 0 << ' ';
}
void graph::BellmanFord( int src ){
    vector < int > dist(nodes+1, INF);
    vector < int > visCount(nodes+1, 0);
    vector < bool > inQ( nodes+1, 0);
    queue < int > Q; dist[src] = 0;
    Q.push( src ); int nod;
    bool negativeCicle = false; while( !Q.empty() && !negativeCicle ){
        nod = Q.front();
        Q.pop();
        inQ[nod] = false; for( int i = 0; i < Ad[nod].size(); ++i ){
            int w = Ad[nod][i];
            int dw = EdgeValue[nod][i]; if( dist[w] > dist[nod] + dw ){
                dist[w] = dist[nod] + dw;
//cout << nod << ' ' << w << ' ' << dist[w] << '\n'; if( inQ[w] == false ){
                inQ[w] = true;
                Q.push( w );
            }
            visCount[w]++;
            if( visCount[w] == nodes ){
                negativeCicle = true;
                break;
            }
        }
    }
    if( negativeCicle == true )
        fout << "Ciclu negativ!\n";
    else{
        for( int i = 1; i <= nodes; ++i )
            if( i != src )
                fout << dist[i] << ' ';
        fout << '\n';
    }
}
void graph::TopoDFS( int nod, vector < bool > & vis, stack < int > & Topo ){ vis[nod] = 1;
    for( int i = 0; i < Ad[nod].size(); ++i ){
        int w = Ad[nod][i];
        if( !vis[w] )
            TopoDFS( w, vis, Topo );
    }
    Topo.push(nod);}
void graph :: TopoSort(){
    vector < bool > vis(nodes+1, 0);
    stack < int > Topo; for( int i = 1; i <= nodes; ++i )
        if( !vis[i] )
            TopoDFS( i, vis, Topo ); while( !Topo.empty() ){
        fout << Topo.top() << ' ';
        Topo.pop();
    }
}
vector < vector < int > > graph::StronglyConnectedComponents(){
    vector < vector < int > > Ad_r;
    Ad_r.resize(nodes+1);
    for( int i = 1; i <= nodes; ++i )
        for( int j = 0; j < Ad[i].size(); ++j)
            Ad_r[Ad[i][j]].push_back(i); stack < int > Topo;
    vector < bool > vis(nodes+1, 0);
    for( int i = 1; i <= nodes; ++i )
        if( !vis[i] )
            TopoDFS( i, vis, Topo ); vector < vector < int > > scc;
    fill(vis.begin(), vis.end(), 0);
    while( !Topo.empty() ){ if( !vis[Topo.top()] ){
            vector < int > comp;
            DFS_r( Topo.top(), vis, Ad_r, comp);
            scc.push_back( comp );
        }
        Topo.pop();
    }
    return scc;
}
int** graph::RoyFloyd(){ int** RF = new int* [nodes+1];
    for( int i = 1; i <= nodes; ++i ){
        RF[i] = new int [nodes+1];
        for( int j = 1; j <= nodes; ++j )
            RF[i][j] = INF;
        RF[i][i] = 0;
    } for( int i = 1; i <= nodes; ++i )
        for( int j = 0; j < Ad[i].size(); ++j )
            RF[i][Ad[i][j]] = EdgeValue[i][j]; for( int k = 1; k <= nodes; ++k )
        for( int i = 1; i <= nodes; ++i )
            for( int j = 1; j <= nodes; ++j )
                if( RF[i][j] > (1LL * RF[i][k] + RF[k][j]) )
                    RF[i][j] = RF[i][k] + RF[k][j]; for( int i = 1; i <= nodes; ++i )
        for( int j = 1; j <= nodes; ++j )
            if( RF[i][j] == INF )
                RF[i][j] = 0; return RF;
}
void graph::DFS_diameter( int nod, int parent, int lg, int& lgmax, int& last ){
    if( lg > lgmax ){
        lgmax = lg;
        last = nod;
    } for( int i = 0; i < Ad[nod].size(); ++i )
        if( Ad[nod][i] != parent )
            DFS_diameter( Ad[nod][i], nod, lg+1, lgmax, last );
}
int graph::Diameter(){
    int lgmax = 0;
    int last; DFS_diameter( 1, 0, 1, lgmax, last );
    lgmax = 0;
    DFS_diameter( last, 0, 1, lgmax, last ); return lgmax;
}
bool graph::BFSflow(int source, int sync, const vector < vector < int > > & AdRes, int **cap, int **flow, int *parent){
    for( int i = 1; i <= nodes; ++i ) parent[i] = 0;
    queue < int > Q;
    Q.push( source );
    int nod; parent[source] = -1; while( !Q.empty() ){
        nod = Q.front();
        Q.pop(); if( nod == sync ) continue; for( int i = 0; i < AdRes[nod].size(); ++i ){
            int w = AdRes[nod][i]; if( !parent[w] && cap[nod][w] - flow[nod][w] > 0 ){
                parent[w] = nod;
                Q.push( w );
            }
        }
    } return (parent[sync] != 0);
}
int graph::MaxFlow( int source, int sync ) {
    vector < vector < int > > AdRes;
    AdRes.resize(nodes+1); int** cap = new int* [nodes+1];
    int** flow = new int* [nodes+1];
    for( int i = 1; i <= nodes; ++i ){
        cap[i] = new int [nodes+1];
        flow[i] = new int [nodes+1];
        for( int j = 1; j <= nodes; ++j )
            cap[i][j] = flow[i][j] = 0;
    } for( int i = 1; i <= nodes; ++i )
        for( int j = 0; j < Ad[i].size(); ++j ){
            AdRes[i].push_back(Ad[i][j]);
            AdRes[Ad[i][j]].push_back(i);
            cap[i][Ad[i][j]] = EdgeValue[i][j];
        } int* parent = new int [nodes+1];
    int totalFlow = 0; while( BFSflow(source, sync, AdRes, cap, flow, parent) ){ for( int i = 0; i < AdRes[sync].size(); ++i ){
            int w = AdRes[sync][i]; if( parent[w] && cap[w][sync] - flow[w][sync] > 0 ){
                parent[sync] = w;
                int flowBottleneck = INF; for( int nod = sync; nod != source; nod = parent[nod] )
                    flowBottleneck = min( flowBottleneck, cap[parent[nod]][nod] - flow[parent[nod]][nod] ); for( int nod = sync; nod != source; nod = parent[nod] ) {
                    flow[parent[nod]][nod] += flowBottleneck;
                    flow[nod][parent[nod]] -= flowBottleneck;
                }
                totalFlow += flowBottleneck;
            }
        }
    } for( int i = 1; i <= nodes; ++i ){
        delete [] cap[i];
        delete [] flow[i];
    }
    delete [] cap;
    delete [] flow;
    delete [] parent; return totalFlow;
}
int main()
{
    int n, m, x, y, c;
    vector < vector < int > > Ad;
    vector < vector < int > > Cost;

    fin >> n >> m;

    Ad.resize(n + 1);
    Cost.resize(n + 1);

    for(int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> c;

        Ad[x].push_back(y);
        Cost[x].push_back(c);
    }

    graph G(n, m, Ad, Cost);

    fout << G.MaxFlow(1, n);

    return 0;
}