#include <bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0
#define ll long long

const int N = 405;
int n, m;
int E[N];
int u[N], v[N], c[N];

namespace Sub1 {
	int id[105][20];
	int cnt = 0;
	bool vis[105];
	void solve() {
		for (int i = 0; i < n; i++) {
			for (int j = 1; j <= E[i]; j++) id[i][j] = ++cnt;
		}
		int ans = 0;
		for (int s = 0; s < (1 << cnt); s++) {
			int tot = 0;
			for (int i = 0; i < cnt; i++) {
				if (s & (1 << i)) vis[i + 1] = 1, tot++;
				else vis[i + 1] = 0;
			}
			int flag = 1;
			for (int i = 1; i <= m; i++) {
				int u = ::u[i], v = ::v[i], c = ::c[i];
				int x = id[c][u], y = id[(c + 1) % n][v];
				if (vis[x] && vis[y]) {flag = 0; break;}
			}
			if (flag) ans = max(ans, tot);
		}
		cout << ans << '\n';
	}
}

namespace Sub2 {
	int f[55][1 << 8];
	int g[1 << 8];
	int mask[55][1 << 8];
	vector < pair <int, int> > e[55];
	void solve() {
		for (int i = 1; i <= m; i++) {
			u[i]--, v[i]--;
			e[c[i]].push_back({u[i], v[i]});
		}
		for (int i = 0; i < n; i++) {
			for (int s = 0; s < (1 << E[i]); s++) {
				int t = 0;
				for (auto qwq : e[i]) {
					int x = qwq.first, y = qwq.second;
					if (s & (1 << x)) t |= (1 << y);
				}
				t ^= ((1 << E[(i + 1) % n]) - 1);
				mask[i][s] = t;
			}
		}
		int ans = 0;
		for (int S = 0; S < (1 << E[0]); S++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < (1 << E[i]); j++) {
					f[i][j] = -1e9;
				}
			}
			f[0][S] = __builtin_popcount(S);
			for (int i = 0; i < n - 1; i++) {
				for (int s = 0; s < (1 << E[i + 1]); s++) g[s] = -1e9;
				for (int s = 0; s < (1 << E[i]); s++) {
					if (f[i][s] < 0) continue;
					g[mask[i][s]] = max(g[mask[i][s]], f[i][s]);
				}
//				for (int s = 0; s < (1 << E[i + 1]); s++) cout << g[s] << ' ';
//				cout << endl;
				for (int j = 0; j < E[i + 1]; j++) {
					for (int s = (1 << E[i + 1]) - 1; s >= 0; s--) {
						if (!(s & (1 << j))) g[s] = max(g[s], g[s ^ (1 << j)]);
					}
				}
				for (int s = 0; s < (1 << E[i + 1]); s++) f[i + 1][s] = g[s] + __builtin_popcount(s);
				//cout << endl;
			}
			for (int s = 0; s < (1 << E[n - 1]); s++) {
				if ((mask[n - 1][s] & S) == S) ans = max(ans, f[n - 1][s]);
			}
		}
		cout << ans << '\n';
	}
}

namespace Sub3 {
	int pos[105];
	int id[105][105];
	bitset <105> mask[105], qwq;
	int tot = 0;
	int cal() {
		qwq.reset();
		int sum = 0;
		for (int i = 1; i <= tot; i++) {
			if (!((qwq & mask[pos[i]]).any())) sum++, qwq.set(pos[i]);
		}
		return sum;
	}
	mt19937 rnd(time(0));
	int now = 0, ans = 0;
	void SA(double t) {
		while (t > 1e-3) {
			int u = rnd() % tot + 1, v = rnd() % tot + 1;
			swap(pos[u], pos[v]);
			int res = cal();
			ans = max(ans, res);
			if (res > now || exp(-1.0 * (now - res) / t) > rnd() / UINT_MAX) now = res;
			else swap(pos[u], pos[v]);
			t *= 0.997;
		}
	}
	void solve() {
		for (int i = 0; i < n; i++) {
			for (int j = 1; j <= E[i]; j++) {
				id[i][j] = ++tot;
			}
		}
		//cout << tot << endl;
		for (int i = 1; i <= m; i++) {
			int uu = u[i], vv = v[i];
			uu = id[c[i]][uu], vv = id[(c[i] + 1) % n][vv];
			//cout << uu << ' ' << vv << endl;
			mask[uu].set(vv);
			mask[vv].set(uu);
		}
		for (int i = 1; i <= tot; i++) pos[i] = i;
		shuffle(pos + 1, pos + tot + 1, rnd);
		ans = now = cal();
		while (1.0 * clock() / CLOCKS_PER_SEC < 0.9) SA(1000000);
		cout << ans;
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> u[i] >> v[i] >> c[i];
		c[i]--;
		E[c[i]] = max(E[c[i]], u[i]);
		E[(c[i] + 1) % n] = max(E[(c[i] + 1) % n], v[i]);
	}
	int sum = 0, mx = 0;
	for (int i = 0; i < n; i++) sum += E[i], mx = max(mx, E[i]);
	if (sum <= 11 && m <= 11) Sub1 :: solve();
	else if (sum <= 100 && mx <= 8) Sub2 :: solve();
	else Sub3 :: solve();
	QwQ330AwA;
}