#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int MAXN = 2000;
int in[MAXN];
array<int, 2> pairs[MAXN];
int col[MAXN];
vector<int> in_col[MAXN];

vector<array<int, 2>> g[MAXN];
int tin[MAXN], tout[MAXN], comp[MAXN];
int tim = 0;
int p[MAXN], pe[MAXN];

void dfs(int v, int c, int dfs_p = -1) {
    tin[v] = tim++;
    comp[v] = c;
    for (auto e : g[v]) {
        int u = e[0];
        if (u != dfs_p) {
            p[u] = v;
            pe[v] = e[1];
            dfs(u, c, v);
        }
    }
    tout[v] = tim++;
}

bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int par[MAXN], sz[MAXN];
int dsu_id[MAXN];

int get(int v) {
    return v == p[v] ? v : p[v] = get(p[v]);
}

void join(int u, int v) {
    u = get(u);
    v = get(v);
    int res_id = dsu_id[u];
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    p[v] = u;
    dsu_id[u] = res_id;
}

int d[MAXN], prevd[MAXN];

int used_col[MAXN];

int went_col[MAXN];

bool go(int n, int m) {
    for (int i = 0; i < n; ++i) {
        g[i].clear();
    }
    fill(used_col, used_col + n + 1, 0);
    fill(went_col, went_col + n + 1, 0);
    for (int j = 0; j < m; ++j) {
        if (in[j]) {
            int u = pairs[j][0], v = pairs[j][1];
            g[u].push_back({v, j});
            g[v].push_back({u, j});
            used_col[col[j]] = 1;
        }
    }
    fill(comp, comp + n, -1);
    tim = 0;
    int c = 0;
    for (int i = 0; i < n; ++i) {
        if (comp[i] == -1) {
            p[i] = -1;
            dfs(i, c++);
        }
    }
    fill(sz, sz + n, 0);
    iota(par, par + n, 0);
    iota(dsu_id, dsu_id + n, 0);

    deque<int> q;
    fill(d, d + m, m);
    fill(prevd, prevd + m, -1);
    for (int i = 0; i < m; ++i) {
        if (!used_col[col[i]]) {
            q.push_back(i);
            d[i] = 0;
        }
    }
    while (!q.empty()) {
        int id = q.front();
        q.pop_front();
        if (!in[id]) {
            int u = pairs[id][0], v = pairs[id][1];
            if (col[u] != col[v]) {
                for (int i = d[id]; i >= 0; --i) {
                    in[id] ^= 1;
                    id = prevd[id];
                }
                return true;
            }
            u = dsu_id[get(u)];
            v = dsu_id[get(v)];
            while (!is_anc(u, v)) {
                int jd = pe[u];
                d[jd] = d[id] + 1;
                prevd[jd] = id;
                q.push_back(jd);
                join(p[u], u);
                u = dsu_id[get(u)];
            }
            while (!is_anc(v, u)) {
                int jd = pe[v];
                d[jd] = d[id] + 1;
                prevd[jd] = id;
                q.push_back(jd);
                join(p[v], v);
                v = dsu_id[get(v)];
            }
        } else {
            if (!went_col[col[id]]) {
                went_col[col[id]] = true;
                for (int jd : in_col[col[id]]) {
                    if (!in[jd]) {
                        d[jd] = d[id] + 1;
                        prevd[jd] = id;
                        q.push_back(jd);
                    }
                }
            }
        }
    }
    return false;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> ed(m);
    for (int i = 0; i < m; ++i) {
        cin >> ed[i][1] >> ed[i][2] >> ed[i][0];
        --ed[i][1];
        --ed[i][2];
    }

    sort(ed.begin(), ed.end());
    for (int i = 0; i < m; ++i) {
        pairs[i] = {ed[i][1], ed[i][2]};
        col[i] = ed[i][0];
        in_col[col[i]].push_back(i);
    }
    int cur_m = 0;
    for (int i = 0; i <= n + 1; ++i) {
        cur_m += in_col[i].size();
        while (go(n, cur_m)) {}
        int sz = 0;
        for (int i = 0; i < cur_m; ++i) {
            sz += in[i];
        }
        if (sz <= i) {
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}