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

int bfs(int s,int d)
{
    for(int i=0;i<=n;i++)
        viz[i]=0;
    viz[s]=1;
    q.push(s);
    ///folosesc bfs pt a determina daca exista drumuri posibile
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        if(d==nod)
            continue;
       // cout<<nod<<'\n';
        for(auto i:v[nod])
            if(flow[nod][i]<c[nod][i]&&!viz[i])
            {
                viz[i]=1;
                pr[i]=nod;
                q.push(i);
            }
    }

    return viz[d];
}

void solve(int s,int d)
{
    ///cat timp se poate mari fluxul continui
    while(bfs(s,d))
    {
     //  cout<<'z'<<'\n';
        for(auto i:v[d])
            if(viz[i])
            {
                ///parcurg toate traseele posibile pt a determina fluxul
                pr[d]=i;
                int z=d,mi=2e9;
                while(z!=s&&mi>0)
                {
                    int f=pr[z];
                    int g=z;
                    mi=min(mi,c[f][g]-flow[f][g]);
                    z=pr[z];
                   // cout<<z<<'\n';
                }
                if(mi<=0)
                    continue;
                z=d;
                sol+=mi;

                ///modific fluxul muchiilor folosite
                while(z!=s)
                {
                    int f=pr[z];
                    int g=z;
                    flow[f][g]+=mi;
                    flow[g][f]-=mi;
                    z=pr[z];
                }
            }
    }
}

int main()
{
    cout<<1<<'\n';
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    fin>>n>>m;
    cout<<n<<'\n';
    ///salvez graful
    for(int i=1;i<=m;i++)
    {
        fin>>f>>g;
        fin>>c[f][g];
        v[f].pb(g);
        v[g].pb(f);
    }
    ///determin fluxul maxim
    solve(1,n);
    cout<<sol<<'\n';
    fout<<sol;
}