/*
**  NOT FOR REVIEW JUST ALGO TEST
**
**
**
*/

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <fstream>

using namespace std;

const long long inf = 1e18;

struct edge {
	long long u, v, f, c;
	edge() {}
	edge(long long u_, long long v_, long long f_, long long c_) {
		this->u = u_;
		this->v = v_;
		this->f = f_;
		this->c = c_;
	}
};

long long n, m, s, t;
vector <edge> e;
vector <long long> next_;
vector <long long> head;

vector <long long> dist;

//slice
vector <long long> next_right;
vector <long long> prev_right;
vector <long long> head_right;

vector <long long> next_left;
vector <long long> prev_left;
vector <long long> head_left;
 

vector <long long> pout;
vector <long long> pin;
vector <long long> excess;
vector <long long> alreadyDel;

bool buildSlice() {
	dist.assign(n, -1);
	queue <int> q;

	q.push(s);
	dist[s] = 0;

	while (!q.empty()) {
		int u = q.front();
		q.pop();

		int ptr = head[u];
		while (ptr != -1) {
			if (e[ptr].c > e[ptr].f && dist[e[ptr].v] == -1) {
				dist[e[ptr].v] = 1 + dist[u];
				q.push(e[ptr].v);
			}

			ptr = next_[ptr];
		}
	}


	return dist[t] != -1;
}

void countPotential() {
	pout.assign(n, 0);
	pin.assign(n, 0);

	for (int i = 0; i < e.size(); ++i) {
		if (dist[e[i].u] + 1 == dist[e[i].v]) {
			pout[e[i].u] += e[i].c - e[i].f;
			pin[e[i].v] += e[i].c - e[i].f;
		}
	}

	pin[s] = inf;
	pout[t] = inf;
}


void getSlice() {
	prev_right.assign(2 * m, -1);
	next_right.assign(2 * m, -1);
	head_right.assign(n, -1);

	prev_left.assign(2 * m, -1);
	next_left.assign(2 * m, -1);
	head_left.assign(n, -1);

	for (int i = 0; i < e.size(); ++i) {
		if (dist[e[i].u] + 1 == dist[e[i].v]) {
			//add to doublelinked list right and left

			if (head_right[e[i].u] != -1) {
				prev_right[head_right[e[i].u]] = i;
			}
			next_right[i] = head_right[e[i].u];
			head_right[e[i].u] = i;

			int j = i ^ 1;
			if (head_left[e[j].u] != -1) {
				prev_left[head_left[e[j].u]] = j;
			}
			next_left[j] = head_left[e[j].u];
			head_left[e[j].u] = j;
		}
	}
}

void deleteEdge(int ind) {
	int back = ind ^ 1;

	int preve = prev_right[ind];
	int nexte = next_right[ind];
	if (preve == -1) head_right[e[ind].u] = nexte;
	if (preve != -1) next_right[preve] = nexte;
	if (nexte != -1) prev_right[nexte] = preve;


	preve = prev_left[back];
	nexte = next_left[back];
	if (preve == -1) head_left[e[back].u] = nexte;
	if (preve != -1) next_left[preve] = nexte;
	if (nexte != -1) prev_left[nexte] = preve;
}

void deleteVert(int u) {
	if (alreadyDel[u]) return;

	alreadyDel[u]++;

	queue<int> qdel;
	int ptr = head_right[u];
	while (ptr != -1) {
		int step = next_right[ptr];

		pin[e[ptr].v] -= e[ptr].c - e[ptr].f;

		if (min(pin[e[ptr].v], pout[e[ptr].v]) <= 0) qdel.push(e[ptr].v);

		deleteEdge(ptr);

		ptr = step;
	}


	int ptr1 = head_left[u];
	while (ptr1 != -1) {
		int step = next_left[ptr1];
		ptr = ptr1 ^ 1;

		pout[e[ptr].u] -= e[ptr].c - e[ptr].f;

		if (min(pin[e[ptr].u], pout[e[ptr].u]) <= 0) qdel.push(e[ptr].u);

		deleteEdge(ptr);

		ptr1 = step;
	}

	while (!qdel.empty()) {
		deleteVert(qdel.front());
		qdel.pop();
	}
}

void deleteNull() {
	queue<int> q;
	for (int i = 0; i < n; ++i) {
		if (min(pout[i], pin[i]) <= 0 && dist[i] != -1) { //??
			q.push(i);
		}
	}

	while (!q.empty()) {
		deleteVert(q.front());
		q.pop();
	}
}

int findMin() {
	int ind = -1;

	for (int i = 0; i < n; ++i) {
		if (min(pout[i], pin[i]) > 0 && (ind == -1 || min(pout[i], pin[i]) < min(pout[ind], pin[ind])))
			ind = i;
	}

	return ind;
}

void goRight(int start) {
	queue<int> q;
	q.push(start);

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (u == t) return;
		int ptr = head_right[u];
		while (ptr != -1 && excess[u] > 0) {
			int step = next_right[ptr];

			long long razn = e[ptr].c - e[ptr].f;
			int minpush = min(excess[u], razn);

			e[ptr].f += minpush;
			e[ptr ^ 1].f -= minpush;

			pout[u] -= minpush;
			pin[e[ptr].v] -= minpush;

			excess[e[ptr].v] += minpush;
			excess[u] -= minpush;

			if (e[ptr].c <= e[ptr].f) deleteEdge(ptr);

			q.push(e[ptr].v);

			ptr = step;
		}
	}

}

void goLeft(int start) {
	queue<int> q;
	q.push(start);


	while (!q.empty()) {
		int v = q.front();
		q.pop();
		if (v == s) return;
		int ptr1 = head_left[v];
		int ptr = ptr1 ^ 1;
		while (ptr1 != -1 && excess[v]) {
			ptr = ptr1 ^ 1;
			int step = next_left[ptr1];

			long long razn = e[ptr].c - e[ptr].f;
			int minpush = min(excess[v], razn);

			e[ptr].f += minpush;
			e[ptr ^ 1].f -= minpush;

			pin[v] -= minpush;
			pout[e[ptr].u] -= minpush;

			excess[e[ptr].u] += minpush;
			excess[v] -= minpush;

			if (e[ptr].c <= e[ptr].f) deleteEdge(ptr);

			q.push(e[ptr].u);

			ptr1 = step;
		}
	}

}

long long findFlowMalhotra() {
	while (buildSlice()) {
		getSlice();
		countPotential();
		alreadyDel.assign(n, 0);
		
		while (!alreadyDel[t] && !alreadyDel[s]) {
			deleteNull();
			pout[t] = inf;
			pin[s] = inf;

			int minInd = findMin();

			if (minInd == -1) break;

			int pflow = min(pin[minInd], pout[minInd]);

			excess.assign(n, 0);
			excess[minInd] = pflow;
			goRight(minInd);
			excess[minInd] = pflow;
			goLeft(minInd);
		}
	}

	long long maxFlow = 0;
	long long ptr = head[s];
	while (ptr != -1) {
		maxFlow += e[ptr].f;
		ptr = next_[ptr];
	}
	return maxFlow;
}


void informatics() {
	cin >> n;
	cin >> m;
	s = 0;
	t = n - 1;
	e.assign(2 * m, edge());
	next_.assign(2 * m, -1);
	head.assign(n, -1);

	long long x, y, z;
	for (int i = 0, l = 0; i < m; ++i, l += 2) {
		cin >> x >> y >> z;
		x++;
		y++;
		e[l] = edge(x - 1, y - 1, 0, z);
		next_[l] = head[x - 1];
		head[x - 1] = l;

		e[l + 1] = edge(y - 1, x - 1, 0, 0);
		next_[l + 1] = head[y - 1];
		head[y - 1] = l + 1;
	}

	cout << findFlowMalhotra() << endl;
}

void localTest() {
	ifstream in("big_tests8.txt");
	int iteration = 0;
	in >> n;
	while (n) {

		
		//cout << iteration << "\n";


		in >> m;
		s = 0;
		t = n - 1;
		//cout << n << " " << m << endl;
		e.assign(2 * m, edge());
		next_.assign(2 * m, -1);
		head.assign(n, -1);

		int x, y, z;
		for (int i = 0, l = 0; i < m; ++i, l += 2) {
			in >> x >> y >> z;
			//cout << x << " " << y << " " << z << endl;

			e[l] = edge(x - 1, y - 1, 0, z);
			next_[l] = head[x - 1];
			head[x - 1] = l;

			e[l + 1] = edge(y - 1, x - 1, 0, 0);
			next_[l + 1] = head[y - 1];
			head[y - 1] = l + 1;
		}
		int trueAnsw = 0;
		in >> trueAnsw;

		if (iteration == 8238) {
			cout << iteration << "\n";

			cout << n << " " << m << "\n";
			for (int i = 0, l = 0; i < m; ++i, l += 2) {
				//in >> x >> y >> z;
				cout << e[l].u + 1 << " " << e[l].v + 1 << " " << e[l].c << endl;

				//e[l] = edge(x - 1, y - 1, 0, z);
				//next_[l] = head[x - 1];
				//head[x - 1] = l;

				//e[l + 1] = edge(y - 1, x - 1, 0, 0);
				//next_[l + 1] = head[y - 1];
				//head[y - 1] = l + 1;
			}
			cout << trueAnsw << endl;
		}

		int myFlow = findFlowMalhotra();
		if (myFlow != trueAnsw) {
			/*cout << iteration << "\n";
			
			cout << n << " " << m << "\n";
			for (int i = 0, l = 0; i < m; ++i, l += 2) {
				//in >> x >> y >> z;
				cout << e[i].u + 1 << " " << e[i].v + 1 << " " << e[i].c << endl;

				//e[l] = edge(x - 1, y - 1, 0, z);
				//next_[l] = head[x - 1];
				//head[x - 1] = l;

				//e[l + 1] = edge(y - 1, x - 1, 0, 0);
				//next_[l + 1] = head[y - 1];
				//head[y - 1] = l + 1;
			}*/

			cout << myFlow << " " << trueAnsw << endl;
		}
		//else cout << "OK\n";
		//cout << endl;
		in >> n;
		iteration++;
	}
}

void mathan() {
	int n1;
	cin >> n1;
	int plusSum = 0;
	n = n1 + 2;

	s = 0;
	t = n - 1;

	head.resize(n, -1);
	int cost;
	for (int i = 0; i < n1; ++i) {
		cin >> cost;
		if (cost > 0) {
			plusSum += cost;
		}

		if (cost > 0) {
			e.push_back(edge(s, i+1, 0, cost));
			next_.push_back(head[s]);
			head[s] = e.size() - 1;

			e.push_back(edge(i + 1, s, 0, 0));
			next_.push_back(head[i + 1]);
			head[i + 1] = e.size() - 1;
		}

		else {
			e.push_back(edge(i + 1, t, 0, -cost));
			next_.push_back(head[i + 1]);
			head[i + 1] = e.size() - 1;

			e.push_back(edge(t, i + 1, 0, 0));
			next_.push_back(head[t]);
			head[t] = e.size() - 1;
		}
	}
	
	int num, x;
	for (int i = 0; i < n1; ++i) {
		cin >> num;

		for (int j = 0; j < num; ++j) {
			cin >> x;

			e.push_back(edge(i + 1, x, 0, inf));
			next_.push_back(head[i + 1]);
			head[i + 1] = e.size() - 1;

			e.push_back(edge(x, i + 1, 0, 0));
			next_.push_back(head[x]);
			head[x] = e.size() - 1;
		}
	}
	m = e.size() / 2;
	cout << plusSum - findFlowMalhotra();
}

void e_olymp() {
	cin >> n >> m;

	s = 0;
	t = n - 1;

	e.assign(2 * m, edge());
	next_.assign(2 * m, -1);
	head.assign(n, -1);

	long long x, y, z;
	for (int i = 0, l = 0; i < m; ++i, l += 2) {
		cin >> x >> y >> z;
		e[l] = edge(x - 1, y - 1, 0, z);
		next_[l] = head[x - 1];
		head[x - 1] = l;

		e[l + 1] = edge(y - 1, x - 1, 0, 0); //??? orientir
		next_[l + 1] = head[y - 1];
		head[y - 1] = l + 1;
	}

	cout << findFlowMalhotra() << endl;

	int t;
	cin >> t;
	int type, rx, ry;
	for (int i = 0; i < t; ++i) {
		cin >> type >> rx >> ry;
		rx--;
		ry--;
		int ptr = head[rx];
		while (ptr != -1) {
			if (e[ptr].v == ry) {
				if (type == 1) {
					e[ptr].c++;
				}
				else {
					e[ptr].c--;
				}

				for (int j = 0; j < e.size(); ++j) {
					e[j].f = 0;
				}
				break;
			}
			ptr = next_[ptr];
		}

		cout << findFlowMalhotra() << endl;
	}
}

void a_task() {
	cin >> n;
	int x, y, z;
	while (n != 0) {
		cin >> s >> t;
		cin >> m;
		s--;
		t--;

		e.assign(2 * m, edge());
		next_.assign(2 * m, -1);
		head.assign(n, -1);

		for (int i = 0, l = 0; i < m; ++i, l += 2) {
			cin >> x >> y >> z;
			e[l] = edge(x - 1, y - 1, 0, z);
			next_[l] = head[x - 1];
			head[x - 1] = l;

			e[l + 1] = edge(y - 1, x - 1, 0, z);
			next_[l + 1] = head[y - 1];
			head[y - 1] = l + 1;
		}


		cout << findFlowMalhotra() << endl;
		cin >> n;
	}
}

int main() {
	informatics();
	//localTest();
	//mathan();
	//a_task();

	//e_olymp();
	return 0;
}


Measured memory_bytes: 3260