#include <bits/stdc++.h>
const long long HASHMAX = 3;
const int MAXN = 200005;
int numbers[MAXN];
long long hash[15][15][10];
long long tag_hash[15];
long long hash_tmp[15];
int select_index[15];
std::vector<long long> primes(HASHMAX);
long long MOD_MAX = 9999999999997;
int main(int argc, char* argv[]) {
  srand(time(0));
  for (auto i = 0; i < HASHMAX; i++) {
    primes[i] = rand() % 9999997;
  }
  int t;
  long long n, m, k, z;
  scanf("%lld %lld %lld", &n, &m, &k);
  std::vector<std::vector<std::pair<long long, long long>>> out_edges(n + 5);
  long long u, v, w;
  for (auto i = 0; i < m; i++) {
    scanf("%lld %lld %lld", &u, &v, &w);
    out_edges[u].emplace_back(w, v);
  }
  for (auto i = 1; i <= n; i++) {
    sort(out_edges[i].begin(), out_edges[i].end());
    int degree = int(out_edges[i].size());
    for (long long j = 0; j < degree; j++) {
      for (long long ii = 0; ii < HASHMAX; ii++) {
        long long val = out_edges[i][j].second;
        hash[degree][j + 1][ii] += (val * (primes[ii] + val) +
                                    (val * val * (val + primes[ii])) % MOD_MAX);
      }
    }
  }
  for (long long j = 0; j < HASHMAX; j++)
    for (long long i = 1; i <= n; i++) {
      {
        tag_hash[j] +=
            (i * (primes[j] + i) + (i * i * (primes[j] + i)) % MOD_MAX);
      }
    }
  long long cnt_res = 0;
  for (auto i = 1; i <= k; i++) {
    select_index[i] = 1;
  }
  while (!select_index[k + 1]) {
    bool ok_tag = true;
    for (auto i = 0; i < HASHMAX; i++) {
      hash_tmp[i] = 0;
    }
    for (auto i = 1; i <= k; i++) {
      for (auto j = 0; j < HASHMAX; j++) {
        hash_tmp[j] += hash[i][select_index[i]][j];
      }
    }
    for (auto i = 0; i < HASHMAX; i++) {
      if (hash_tmp[i] != tag_hash[i]) {
        ok_tag = false;
        break;
      }
    }
    if (ok_tag) {
      cnt_res++;
    }
    select_index[1]++;
    int index_now = 1;
    while (select_index[index_now] > index_now) {
      select_index[index_now] = 1;
      select_index[index_now + 1]++;
      index_now++;
    }
  }
  printf("%lld\n", cnt_res);
  return 0;
}
