#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int K = 10;
int cnt[N], w[10], deg[N], nGd[K][K][K][K], chk[K][K];
vector<int> G[K];
vector<pair<int, int> > E[N];
bitset<N> U[K][K];
int n, m, k, res;
void dfs(int x) {
  if (x == k + 1) {
    ++res;
    return;
  }
  for (int i = 1; i <= x; ++i) {
    if (chk[x][i]) continue;
    int ok = 0;
    for (int j = 1; j < x; ++j) {
      if (nGd[x][i][j][w[j]]) {
        ok = 1;
        break;
      }
    }
    if (ok) continue;
    w[x] = i;
    dfs(x + 1);
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; ++i) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    E[x].push_back(make_pair(z, y));
    ++deg[x];
  }
  for (int i = 1; i <= n; ++i) {
    sort(E[i].begin(), E[i].end());
    G[deg[i]].push_back(i);
  }
  for (int i = 1; i <= k; ++i) {
    for (int j = 1; j <= i; ++j) {
      U[i][j].reset();
      for (int ii = 1; ii <= n; ++ii) cnt[ii] = 0;
      for (auto& x : G[i]) {
        int y = E[x][j - 1].second;
        ++cnt[y];
        if (cnt[y] > 1) chk[i][j] = 1;
        U[i][j][y] = 1;
      }
    }
  }
  for (int i = 1; i <= k; ++i) {
    for (int j = 1; j <= i; ++j) {
      for (int ii = i + 1; ii <= k; ++ii) {
        for (int jj = 1; jj <= ii; ++jj) {
          if ((U[i][j] & U[ii][jj]).count()) {
            nGd[i][j][ii][jj] = nGd[ii][jj][i][j] = 1;
          }
        }
      }
    }
  }
  dfs(1);
  printf("%d", res);
  return 0;
}
