#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<int >v[DN];
priority_queue<int>q;

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



void pompare(int f,int g)
{
    int val=c[f][g]-flow[f][g];
    val=min(val,r[f]);
    //if(c[f][g]>0)
        flow[f][g]+=val;
    //else
        flow[g][f]-=val;
    r[f]-=val;
    r[g]+=val;


}

int inaltare(int nod)
{
    if(nod==s||nod==d)
        return 0;

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

        if(h[nod]>h[i])
            return 0;
    }

    int t=2e9;

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

        t=min(t,h[i]+1);
    }
    cout<<nod<<' '<<t<<' '<<r[d]<<'\n';
    h[nod]=t;
    if(t==2e9)
        return 0;
    h[nod]=t;
    return 1;
}

int upd(int nod)
{
    int vf=0;

        //cout<<'z'<<' '<<nod<<' '<<r[nod]<<' '<<r[d]<<'\n';

        for(auto i:v[nod])
        {
            if(h[nod]<h[i]+1)
                continue;

            if(flow[nod][i]==c[nod][i])
                continue;

            pompare(nod,i);
            vf=1;
        }
    return vf;
}

void solve()
{
    h[s]=n;
    for(auto i:v[s])
    {
        r[s]-=c[s][i];
        flow[s][i]=c[s][i];
        r[i]=c[s][i];
    }

    int vf=1;
    while(vf)
    {
        vf=0;
        int nod=s;

        for(nod=s;nod<=d;nod++)
        {
            if(nod==s||nod==d)
                continue;
          //  cout<<'z'<<nod<<'\n';
            if(r[nod]==0)
                continue;
            //vf=inaltare(nod);
            //if(vf)
              //  break;
            vf=max(vf,upd(nod));
        }
        cout<<vf<<'\n';
        //if(vf)
          //  continue;
        for(nod=s;nod<=d;nod++)
        {
            if(nod==s||nod==d)
                continue;
            //cout<<nod<<'\n';
            //if(r[nod]==0)
              //  continue;
            vf=max(vf,inaltare(nod));

        }

        cout<<'z'<<' '<<vf<<'\n';
    }
    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);
        v[g].pb(f);
    }
    s=1;
    d=n;
    solve();
    fout<<sol;
}