3 types

//============================================================================
// Name        : ACM
// Author      : Tarango Khan
// Team        : BRACU Byteheads
//============================================================================

#include <bits/stdc++.h>
using namespace std;
#define Size 100000005
#define Mod 1000000007

struct edge {
    int u;
    int v;
    int w;
};

bool cmp(edge a, edge b) {
    if (a.w == 3) return true;
    return false;
}

int N, M;
edge A[10005];
int men[1005];
int women[1005];

int get_parent_men(int u) {
    if (men[u] == u) return u;
    return men[u] = get_parent_men(men[u]);
}

int get_parent_women(int u) {
    if (women[u] == u) return u;
    return women[u] = get_parent_women(women[u]);
}

int mst() {
    for (int i = 0; i <= N; i++) {
        men[i] = women[i] = i;
    }
    sort(A, A + M, cmp);
    int taken = 0, m = 0, w = 0;
    for (int i = 0; i < M; i++) {
        if (A[i].w == 3) {
            int pu = get_parent_men(A[i].u);
            int pv = get_parent_men(A[i].v);
            if ((pu == pv) || (m >= N - 1 && w >= N - 1)) {
                taken++;
            } else {
                men[pu] = pv;
                women[pu] = pv;
                w++;
                m++;
            }
        }
    }
    for (int i = 0; i < M; i++) {
        if (A[i].w == 1) {
            int pu = get_parent_men(A[i].u);
            int pv = get_parent_men(A[i].v);
            if (pu != pv && m < N - 1) {
                men[pu] = pv;
                m++;
            } else {
                taken++;
            }
        }
    }
    for (int i = 0; i < M; i++) {
        if (A[i].w == 2) {
            int pu = get_parent_women(A[i].u);
            int pv = get_parent_women(A[i].v);
            if (pu != pv && w < N - 1) {
                women[pu] = pv;
                w++;
            } else {
                taken++;
            }
        }
    }
    if (m != N - 1 || w != N - 1) return -1;
    return taken;
}

int main() {
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &A[i].u, &A[i].v, &A[i].w);
            A[i].u--, A[i].v--;
        }
        int res = mst();
        printf("%d\n", res);
    }
    return 0;
}