#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int C = 2e7 + 10, N = 2e5 + 10;
int mod;
const int K = 9;
int p[C];
int h[K][K];
int need, ans;
int n, m, k;
vector<int> primes;
vector<pair<int, int> > g[N];
void calc() {
  auto is_prime = [&](int x) {
    for (int i = 2; i * i <= x; i++)
      if (x % i == 0) return false;
    return true;
  };
  mod = rnd() % (int)(1e9 + 7) + (int)1e8;
  while (!is_prime(mod)) mod++;
  for (int i = 2; i < C; i++) {
    if (p[i]) continue;
    primes.push_back(i);
    for (int j = i * 2; j < C; j += i) p[j] = 1;
  }
}
void rec(int pos, int msk) {
  if (pos == k) {
    if (msk == need) ans++;
    return;
  }
  for (int i = 0; i <= pos; i++) rec(pos + 1, 1ll * msk * h[pos][i] % mod);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  calc();
  cin >> n >> m >> k;
  while (m--) {
    int x, y, w;
    cin >> x >> y >> w;
    g[--x].push_back({--y, w});
  }
  for (int i = 0; i < K; i++)
    for (int j = 0; j < K; j++) h[i][j] = 1;
  for (int v = 0; v < n; v++) {
    sort((g[v]).begin(), (g[v]).end(), [&](pair<int, int> a, pair<int, int> b) {
      return a.second < b.second;
    });
    int pw = (int)(g[v]).size() - 1;
    for (int i = 0; i < (int)(g[v]).size(); i++) {
      int to = g[v][i].first;
      h[pw][i] = 1ll * h[pw][i] * primes[to] % mod;
    }
  }
  need = 1;
  for (int i = 0; i < n; i++) need = 1ll * need * primes[i] % mod;
  rec(0, 1);
  cout << ans;
  return 0;
}
