#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define all(a) begin(a), end(a)
template <class T> bool chmin(T& a, T b) {
  if (a <= b)
    return 0;
  a = b;
  return 1;
}
template <class T> bool chmax(T& a, T b) {
  if (a >= b)
    return 0;
  a = b;
  return 1;
}

ll solve() {
  ll n, m;
  cin >> n >> m;
  array<vector<vector<ll>>, 2> g;
  g[0].resize(n), g[1].resize(n);
  rep(i, 0, m) {
    ll u, v, c;
    cin >> u >> v >> c;
    u--, v--;
    g[c][u].push_back(v);
    g[c][v].push_back(u);
  }

  vector<int> live(n, true);
  rep(v, 0, n) {
    if (g[0][v].empty() || g[1][v].empty()) {
      live[v] = false;
    }
  }

  using S = array<int, 4>;
  const S emp = { -1, -1, -1, -1 };
  array<vector<S>, 2> ans;

  auto add = [&](ll color, S a) {
    sort(all(a));
    ans[color].push_back(a);
  };

  // get all connected subsets
  rep(color, 0, 2) {
    vector<int> visited(n, false);
    rep(root, 0, n) {
      if (!live[root] || visited[root])
        continue;
      visited[root] = true;
      vector<ll> l, r;
      l.push_back(root);
      auto f = [&](auto& f, ll v) -> void {
        if (!live[v] || visited[v])
          return;
        visited[v] = true;
        l.push_back(v);
        for (const ll c : g[color][v])
          f(f, c);
      };
      for (const ll s : g[color][root]) {
        f(f, s);
        swap(l, r);
      }
      vector<ll> vs;
      vs.insert(vs.end(), l.rbegin(), l.rend());
      vs.insert(vs.end(), all(r));
      const int size = vs.size();
      if (g[color][vs.back()].size() == 2) {
        // cycle
        rep(len, 2, 5) {
          if (len > size)
            break;
          if (len == size) {
            S res = emp;
            rep(i, 0, len) res[i] = vs[i];
            add(color, res);
            continue;
          }
          rep(i, 0, size) {
            S res = emp;
            rep(j, 0, len) { res[j] = vs[(i + j) % size]; }
            add(color, res);
          }
        }
      }
      else {
        // path
        rep(len, 2, 5) {
          rep(i, 0, size - len + 1) {
            S res = emp;
            rep(j, 0, len) { res[j] = vs[i + j]; }
            add(color, res);
          }
        }
      }
    }
    sort(all(ans[color]));
  }

  vector<S> inters;
  set_intersection(all(ans[0]), all(ans[1]), back_inserter(inters));
  return inters.size() + n;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T = 1;
  // cin >> T;
  while (T--)
    cout << solve() << endl;
  return 0;
}