Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1000

#define MAXM 10000

struct edges

{

	int u,v,w;

}es[MAXM];

set<int> s;

namespace DINIC

{

	struct edge

	{

		int to,nxt,f;

	}e[MAXM << 2];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b,int f)

	{

		e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

		e[edgenum] = (edge){a,lin[b],f};lin[b] = edgenum++;

		return;

	}

	void init()

	{

		edgenum = 0;

		memset(lin,-1,sizeof(lin));

		return;

	}

	int s,t;

	int ch[MAXN];

	bool BFS()

	{

		memset(ch,-1,sizeof(ch));ch[s] = 0;

		queue<int> q;q.push(s);

		while(!q.empty())

		{

			int k = q.front();q.pop();

			for(int i = lin[k];i != -1;i = e[i].nxt)

			{

				if(ch[e[i].to] == -1 && e[i].f)

				{

					ch[e[i].to] = ch[k] + 1;

					q.push(e[i].to);

				}

			}

		}

		return (ch[t] != -1);

	}

	int flow(int k,int f)

	{

		if(k == t)return f;

		int r = 0;

		for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

		{

			if(ch[e[i].to] == ch[k] + 1 && e[i].f)

			{

				int l = flow(e[i].to,min(e[i].f,f - r));

				e[i].f -= l;r += l;e[i ^ 1].f += l;

			}

		}

		if(r == 0)ch[k] = -1;

		return r;

	}

	#define INF 0x3f3f3f3f

	int dinic()

	{

		int ans = 0,r;

		while(BFS())while(r = flow(s,INF))ans += r;

		return ans;

	}

	int tag[MAXN];

	void mark(int k)

	{

		tag[k] = 1;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(tag[e[i].to] || e[i].f == 0)continue;

			mark(e[i].to);

		}

		return;

	}

}

int p[MAXN],p_[MAXN];

void solve(int l,int r)

{

	if(l == r)return;

	for(int i = 1;i <= n;++i)DINIC::tag[i] = 0;

	DINIC::s = p[l];DINIC::t = p[r];

	DINIC::init();

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

	{

		DINIC::add(es[i].u,es[i].v,es[i].w);

		DINIC::add(es[i].v,es[i].u,es[i].w);

	}

	int val = DINIC::dinic();

	s.insert(val);

	DINIC::mark(DINIC::s);

	int pl = l,pr = r;

	for(int i = l;i <= r;++i)

	{

		if(DINIC::tag[p[i]])p_[pl++] = p[i],DINIC::tag[p[i]] = 0;

		else p_[pr--] = p[i];

	}

	for(int i = l;i <= r;++i)p[i] = p_[i];

	solve(l,pl - 1);solve(pr + 1,r);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].w);

	for(int i = 1;i <= n;++i)p[i] = i;

	solve(1,n);

	cout << s.size() << endl;

	return 0;

}