#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int DN=1005;
int n,m,f,g,s,d;
int dist[DN],viz[DN],pr[DN],c[DN][DN],flow[DN][DN];
long long  sol;
vector<pair<int,int> >v[DN];
priority_queue<int>q;

int r[DN],h[DN];
set<int>sett;



void add(int nod,int val)
{
    if(val==0)
        return;
    r[nod]+=val;
    if(nod==s||nod==d)
        return;

    if(r[nod]==0)
    {
        sett.erase(sett.find(nod));
        return;
    }

    sett.insert(nod);
}

void pompare(int f,int g,int type)
{
    int val=min(r[f],c[f][g]-flow[f][g]);

    if(type==1)
        flow[f][g]+=val;
    else
        flow[g][f]-=val;
    add(f,-val);
    add(g,val);

}

void inaltare(int s)
{
    h[s]=2e9;
    for(auto i:v[s])
    {
        if(flow[s][i.first]==c[s][i.first])
            continue;
        h[s]=min(h[s],h[i.first]+1);
    }
}

void solve()
{
    h[s]=n;
    for(auto i:v[s])
    {
        add(i.first,c[s][i.first]);
    }

    while(!sett.empty())
    {
        int nod=*sett.begin();
        cout<<nod<<' '<<r[nod]<<' '<<r[d]<<'\n';
        int vf=0;
        for(auto i:v[nod])
        {
            if(flow[nod][i.first]==c[nod][i.first])
                continue;

            if(h[nod]!=h[i.first]+1)
                continue;

            vf=1;
            pompare(nod,i.first,i.second);
        }
        if(vf)
            continue;

        //cout<<nod<<' '<<r[nod]<<' '<<r[d]<<'\n';
        inaltare(nod);
        continue;

        for(auto i:v[nod])
        {
            if(flow[nod][i.first]==c[nod][i.first])
                continue;

            if(h[nod]!=h[i.first]+1)
                continue;

            vf=1;
            pompare(nod,i.first,i.second);
        }

        if(!vf)
            sett.erase(sett.find(nod));
    }

    sol=r[d];
}

int main()
{
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>f>>g;
        fin>>c[f][g];
        v[f].pb({g,1});
        v[g].pb({f,0});
    }
    s=1;
    d=n;
    solve();
    fout<<sol;
}