//Code by Patcas Csaba
//Time complexity: O(m^2 log m)
//Space complexity: O(m+n^2)
//Method: Priority-first search
//Working time: 23:40-

#include <stdio.h>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

#define in_file "maxflow.in"
#define out_file "maxflow.out"

#define VI vector <int>

#define FORN(i,n) for (int i=0;i<n;++i)
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define MP make_pair
#define S size()
#define X first
#define Y second

#define inf 111111


int n,m,solution;
vector <VI> c, g;
VI father, d;

void bf()
{
	fill(ALL(d),inf);
	set <pair <int, int> > heap;
	heap.insert(MP(inf,1));
	while (!father[n] && !heap.empty())
	{
		int node=(*heap.rbegin()).Y;
		FORN(i,g[node].S)
		{
			int aux=g[node][i];
			if (!father[aux] && c[node][aux])
			{
				father[aux]=node;
				if (d[aux]>c[node][aux])
				{
					if (d[aux]!=inf) heap.erase(heap.find(MP(d[aux],aux)));
					d[aux]=c[node][aux];
					heap.insert(MP(d[aux],aux));
				}
			}
		}
		heap.erase(heap.find(MP(d[node],node)));
	}
}

int IncreaseFlow()
{
	int node=n, flow=inf;
	while (node!=1)
	{
		flow=min(flow,c[father[node]][node]);
		if (!flow) return 0;
		node=father[node];
	}
	node=n;
	while (node!=1)
	{
		c[father[node]][node]-=flow;
		c[node][father[node]]+=flow;
		node=father[node];
	}
	return flow;
}

void EdmondsKarp()
{
	father.resize(n+1);
	d.resize(n+1);
	solution=0;
	while (1) 
	{
		fill(ALL(father),0);
		bf();
		if (father[n]) 
		{
			FORN(i,g[n].S)
			{
				int q=g[n][i];
				if (father[q])
				{
					father[n]=q;
					int aux=IncreaseFlow();
					solution+=aux;
					cout<<solution<<endl;
				}
			}
		}
		else break;
	}
}

void AddEdge(int node1, int node2, int cc)
{
	g[node1].PB(node2);
	g[node2].PB(node1);
	c[node1][node2]=cc;
}

int main()
{
	FILE* fin=fopen(in_file,"r");
	fscanf(fin,"%d%d",&n,&m);
	g.resize(n+1);
	c.resize(n+1,VI(n+1));
	FORN(q,m)
	{
		int x,y,z;
		fscanf(fin,"%d%d%d",&x,&y,&z);
		AddEdge(x,y,z);
	}
	fclose(fin);

	EdmondsKarp();

	FILE* fout=fopen(out_file,"w");
	fprintf(fout,"%d",solution);
	fclose(fout);

	return 0;
}