#include <bits/stdc++.h>
using namespace std;
const int N = 200'000;
const int S = 2 + 1'100'000;
const int M = 2 * (6'000'000 + 900'000);
const int INF = 1'000'000'000;
int n, m, l[N + 10], r[N + 10], c[N + 10];
int up[N + 10], x[N + 10], y[N + 10];
int idF[4 * N + 10], src, snk, counter;
int e, w[M + 10], pnt[S + 10], h[S + 10];
vector<pair<int, int>> adj[S + 10];
vector<int> vec;
int leaf[N + 10], pre[N + 10], suf[N + 10];
int s[N + 10];
void readInput() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> l[i] >> r[i] >> c[i];
if (l[i] > r[i])
swap(l[i], r[i]);
}
}
void calcIdF(int id = 1, int l = 1, int r = n + 1) {
idF[id] = ++counter;
if (l + 1 == r) {
leaf[l] = idF[id];
return;
}
int mid = (l + r) >> 1;
calcIdF(id << 1, l, mid);
calcIdF(id << 1 | 1, mid, r);
}
void calcVer() {
for (int i = 1; i <= m; i++) {
up[i] = ++counter;
x[i] = ++counter;
y[i] = ++counter;
}
for (int i = 1; i <= n; i++) {
pre[i] = ++counter;
suf[i] = ++counter;
}
calcIdF();
src = ++counter;
snk = ++counter;
}
void addEdge(int e1, int u, int v, int cap) {
w[e1] = cap;
adj[u].push_back({v, e1});
}
void addEdge(int u, int v, int cap) {
int e1 = e, e2 = e + 1;
addEdge(e1, u, v, cap);
addEdge(e2, v, u, 0);
e += 2;
}
void build(int id = 1, int l = 1, int r = n + 1) {
if (l + 1 == r) {
vec.push_back(e);
addEdge(idF[id], snk, 0);
return;
}
int mid = (l + r) >> 1;
addEdge(idF[id], idF[id << 1], INF);
addEdge(idF[id], idF[id << 1 | 1], INF);
build(id << 1, l, mid);
build(id << 1 | 1, mid, r);
}
void add(int st, int en, int val, int id = 1, int l = 1, int r = n + 1) {
if (en <= l || r <= st)
return;
if (st <= l && r <= en) {
addEdge(val, idF[id], INF);
return;
}
int mid = (l + r) >> 1;
add(st, en, val, id << 1, l, mid);
add(st, en, val, id << 1 | 1, mid, r);
}
void addSegEdge(int u, int l, int r) {
if (l <= r)
add(l, r, u);
else {
addEdge(u, suf[l], INF);
if (r != 1)
addEdge(u, pre[r - 1], INF);
}
}
void calcEdge() {
build();
for (int i = 1; i <= m; i++) {
addEdge(src, up[i], 1);
addEdge(up[i], x[i], 1);
addEdge(up[i], y[i], 1);
addSegEdge(x[i], l[i], r[i]);
addSegEdge(y[i], r[i], l[i]);
}
for (int i = 1; i <= n; i++) {
addEdge(pre[i], leaf[i], INF);
addEdge(suf[i], leaf[i], INF);
if (1 < i)
addEdge(pre[i], pre[i - 1], INF);
if (i < n)
addEdge(suf[i], suf[i + 1], INF);
}
}
void initW(int x) {
for (int i = 0; i < e; i += 2) {
w[i] = w[i] + w[i ^ 1];
w[i ^ 1] = 0;
}
for (auto id: vec)
w[id] = x;
}
void initBFS() {
for (int i = 1; i <= snk; i++)
pnt[i] = h[i] = 0;
}
void BFS() {
initBFS();
queue<int> qu;
h[src] = 1;
qu.push(src);
while (!qu.empty()) {
int u = qu.front();
qu.pop();
for (auto [v, e]: adj[u])
if (w[e] && !h[v]) {
h[v] = h[u] + 1;
qu.push(v);
}
}
}
int dfs(int u = src, int x = INF) {
if (u == snk)
return x;
int sum = 0;
while (pnt[u] < adj[u].size()) {
int v = adj[u][pnt[u]].first, e = adj[u][pnt[u]].second;
if (w[e] && h[v] == h[u] + 1) {
int y = min(w[e], x);
int pass = dfs(v, y);
x -= pass;
sum += pass;
w[e] -= pass;
w[e ^ 1] += pass;
if (!x)
break;
}
pnt[u]++;
}
return sum;
}
int dinic(int x) {
int flow = 0;
initW(x);
while (true) {
BFS();
if (!h[snk])
break;
flow += dfs();
cout << x << ' ' << flow << endl;
}
return flow;
}
/*void solve() {
int l = 0, r = m + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (dinic(mid) >= m)
r = mid;
else
l = mid;
}
cout << r << flush;
}*/
void add(int l, int r) {
s[l]++;
if (r < n)
s[r + 1]--;
}
void solve() {
int ans = m;
for (int mask = 0; mask < (1 << m); mask++) {
for (int i = 0; i < m; i++)
if ((mask & (1 << i)))
add(l[i], r[i] - 1);
else {
if (l[i] != 1)
add(1, l[i] - 1);
add(r[i], n);
}
int sum = 0, mx = 0;
for (int i = 1; i <= n; i++) {
sum += s[i];
mx = max(mx, sum);
s[i] = 0;
}
ans = min(ans, mx);
}
cout << ans << flush;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
/*calcVer();
calcEdge();*/
solve();
return 0;
}
