#include <cstdio>
#include <cstring>
#include <climits>
#include <map>
#include <vector>
#include <algorithm>
const int MAX_N = 100;
const int MAX_M = 1000;
const int MOD = 31011;
struct Edge {
    int u, v, w;
    bool vis;
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
} E[MAX_M + 1];
struct UFS {
    int fa[MAX_N + 1];
    void init(int n) {
        for (int i = 0; i <= n; i++) fa[i] = i;
    }
    int find(int x) {
        return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        int f1 = find(x), f2 = find(y);
        fa[f1] = f2;
    }
    bool check(int x, int y) {
        return find(x) == find(y);
    }
} ufs;
struct EdgeGroup {
    int cnt;
    std::vector<Edge> e;
};
int n, m;
bool g[MAX_N + 1][MAX_N + 1];
std::map<int, EdgeGroup> groups;
inline bool kruskal() {
    std::sort(E, E + m);
    ufs.init(n);
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (!ufs.check(E[i].u, E[i].v)) {
            E[i].vis = true;
            ufs.merge(E[i].u, E[i].v);
            groups[E[i].w].cnt++;
            cnt++;
        }
        groups[E[i].w].e.push_back(E[i]);
    }
    return cnt == n - 1;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].w);
    }
    if (!kruskal()) {
        puts("0");
    } else {
        long long ans = 1;
        for (int i = 0; i < m; i++) if (E[i].vis) g[E[i].u][E[i].v] = g[E[i].v][E[i].u] = true;
        for (std::map<int, EdgeGroup>::const_iterator it = groups.begin(); it != groups.end(); it++) {
            if (it->second.cnt == 0) continue;
            int t = 0;
            for (unsigned int s = 1; s < (1 << it->second.e.size()); s++) {
                int tot = 0;
                for (unsigned int i = 0; i < it->second.e.size(); i++) if (s & (1 << i)) tot++;
                if (tot != it->second.cnt) continue;
                for (std::vector<Edge>::const_iterator e = it->second.e.begin(); e != it->second.e.end(); e++) {
                    g[e->u][e->v] = g[e->v][e->u] = false;
                }
                for (unsigned int i = 0; i < it->second.e.size(); i++) {
                    if (s & (1 << i)) g[it->second.e[i].u][it->second.e[i].v] = g[it->second.e[i].v][it->second.e[i].u] = true;
                }
                ufs.init(n);
                for (int i = 1; i <= n; i++) {
                    for (int j = i + 1; j <= n; j++) {
                        if (g[i][j]) {
                            if (ufs.check(i, j)) goto Continue;
                            ufs.merge(i, j);
                        }
                    }
                }
                t++;
Continue:;
            }
//			printf("t = %d\n", t);
            (ans *= t) %= MOD;
            for (std::vector<Edge>::const_iterator e = it->second.e.begin(); e != it->second.e.end(); e++) {
                g[e->u][e->v] = g[e->v][e->u] = e->vis;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}