#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "debug.hpp"
#else
  #define dbg(...) 0
#endif

int solve(const array<vector<vector<int>>, 2>& adj) {
  int n = adj[0].size();
  vector<int> q; q.reserve(n);
  vector<int> remap(n, -1);
  auto check_component = [&](const vector<int>& cc) -> bool {
    int m = cc.size();
    if (m == 1) return true;
    for (int i = 0; i < m; ++i) remap[cc[i]] = i;
    auto clear = [&]() -> void {
      for (int i = 0; i < m; ++i) remap[cc[i]] = -1;
    };
    for (int c = 0; c < 2; ++c) {
      vector<bool> vis(m, false);
      vis[0] = true;
      q.clear();
      q.push_back(0);
      for (int i = 0; i < int(q.size()); ++i) {
        int u = cc[q[i]];
        for (int v0 : adj[c][u]) if (int v = remap[v0]; (v >= 0) && !vis[v]) {
          vis[v] = true;
          q.push_back(v);
        }
      }
      if (int(q.size()) < m) {
        clear();
        return false;
      }
    }
    clear();
    return true;
  };
  array<vector<int>, 2> label;
  array<int, 2> n_cc{0, 0};
  for (int c = 0; c < 2; ++c) {
    label[c].assign(n, -1);
    for (int s = 0; s < n; ++s) if (label[c][s] < 0) {
      q.clear();
      q.push_back(s);
      label[c][s] = n_cc[c]++;
      for (int i = 0; i < int(q.size()); ++i) {
        int u = q[i];
        for (int v : adj[c][u]) {
          if (label[c][v] < 0) {
            label[c][v] = label[c][u];
            q.push_back(v);
          }
        }
      }
    }
  }
  vector<pair<array<int, 2>, int>> both(n);
  for (int i = 0; i < n; ++i) {
    for (int c = 0; c < 2; ++c) {
      both[i].first[c] = label[c][i];
    }
    both[i].second = i;
  }
  sort(both.begin(), both.end());
  int ans = 0;
  int start = 0;
  vector<int> cur; cur.reserve(4);
  vector<int> cc; cc.reserve(4);
  for (int i = 0; i <= n; ++i) {
    if ((i == n) || (both[i].first != both[start].first)) {
      cc.clear();
      for (int j = start; j < i; ++j) {
        cc.push_back(both[j].second);
      }
      int sz = cc.size();
      assert(sz <= 4);
      for (int mask = 1; mask < (1 << sz); ++mask) {
        cur.clear();
        for (int j = 0; j < sz; ++j) {
          if ((mask >> j) & 1) {
            cur.push_back(cc[j]);
          }
        }
        if (check_component(cur)) ans++;
      }
      start = i;
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  array<vector<vector<int>>, 2> adj;
  for (int i = 0; i < 2; ++i) {
    adj[i].resize(n);
  }
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    --u; --v;
    adj[c][u].push_back(v);
    adj[c][v].push_back(u);
  }
  cout << solve(adj) << '\n';
}