#include <cstdio>

#include <cstring>

#include <cassert>

#include <cmath>

#include <algorithm>

using namespace std;

const int NODE_MAX = 1100, EDGE_MAX = 10100, INF = 0x3f3f3f3f;

//below:for dinic-----------------------------------------------------

struct Node;

struct Edge;

struct Node

{

	int Id, Vis;

	int Level;

	Edge *Head;

};

struct Edge

{

	int Cap, Id;

	Edge* Rev, *Next;

	Node *From, *To;

};

Node _nodes[NODE_MAX];

Edge _edges[EDGE_MAX];

int _lastVId, _eCount = 0;

Node *StartNode, *TargetNode;

void Init()

{

	memset(_nodes, 0, sizeof(_nodes));

	memset(_edges, 0, sizeof(_edges));

	_eCount = 0;

}

Edge *NewEdge()

{

	return ++_eCount + _edges;

}

void SetST(int sId, int tId)

{

	StartNode = _nodes + sId;

	TargetNode = _nodes + tId;

}

void SetLastVId(int vId)

{

	_lastVId = vId;

}

Edge *AddEdge(Node *from, Node *to, int id, int cap)

{

	Edge *e = NewEdge();

	e->Id = id;

	e->From = from;

	e->To = to;

	e->Cap = cap;

	e->Next = e->From->Head;

	e->From->Head = e;

	return e;

}

void Build(int uId, int vId, int id, int cap)

{

	Node *u = uId + _nodes, *v = vId + _nodes;

	u->Id = uId;

	v->Id = vId;

	Edge *e1 = AddEdge(u, v, id, cap);

	Edge *e2 = AddEdge(v, u, -id, 0);

	e1->Rev = e2;

	e2->Rev = e1;

}

struct NodeQueue

{

	Node *q[NODE_MAX];

	int head, tail;

	void clear() { head = tail = 0; }

	void push(Node *v) { q[tail++] = v; }

	Node* front() { return q[head]; }

	void pop() { head++; }

	bool empty() { return head == tail; }

};

bool Bfs()

{

	for (int i = 0; i <= _lastVId; i++)

		_nodes[i].Level = 0;

	NodeQueue q;

	q.clear();

	StartNode->Level = 1;

	q.push(StartNode);

	while (!q.empty())

	{

		Node *cur = q.front();

		q.pop();

		for (Edge *e = cur->Head; e; e = e->Next)

		{

			if (!e->To->Level && e->Cap)

			{

				e->To->Level = cur->Level + 1;

				q.push(e->To);

			}

		}

	}

	return TargetNode->Level;

}

int Dfs(Node *cur, int limit)

{

	if (cur == TargetNode)

		return limit;

	if (limit == 0)

		return 0;

	int curTake = 0;

	for (Edge *e = cur->Head; e; e = e->Next)

	{

		if (e->To->Level == cur->Level + 1 && e->Cap)

		{

			int nextTake = Dfs(e->To, min(limit - curTake, e->Cap));

			e->Cap -= nextTake;

			e->Rev->Cap += nextTake;

			curTake += nextTake;

		}

	}

	return curTake;

}

int Dinic()

{

	int ans = 0;

	while (Bfs())

		ans += Dfs(StartNode, INF);

	return ans;

}

//above:for dinic-----------------------------------------------------

void Dfs1(Node *cur)

{

	assert(!cur->Vis);

	cur->Vis = 1;

	for (Edge *e = cur->Head; e; e = e->Next)

		if (e->Cap && !e->To->Vis && e->Id > 0)

			Dfs1(e->To);

}

void Dfs2(Node *cur)

{

	assert(cur->Vis != 1);

	cur->Vis = 2;

	for (Edge *e = cur->Head; e; e = e->Next)

		if (e->Rev->Cap && !e->To->Vis &&e->Rev->Id > 0)

			Dfs2(e->To);

}

int main()

{

	freopen("c:\\noi\\source\\input.txt", "r", stdin);

	int totCity, totEdge;

	scanf("%d%d", &totCity,&totEdge);

	Init();

	SetLastVId(totCity - 1);

	SetST(0, totCity - 1);

	int uId, vId, cap;

	for (int i = 1; i <= totEdge; i++)

	{

		scanf("%d%d%d", &uId, &vId, &cap);

		Build(uId, vId, i, cap);

	}

	Dinic();

	Dfs1(StartNode);

	Dfs2(TargetNode);

	int eId[EDGE_MAX], pe = 0;

	memset(eId, 0, sizeof(eId));

	for (int i = 1; i <= _eCount; i++)

		if (_edges[i].From->Vis == 1 && _edges[i].To->Vis == 2 && _edges[i].Id > 0)

			eId[pe++] = _edges[i].Id;

	sort(eId, eId + pe);

	printf("%d\n", pe);

	return 0;

}