#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)2e5 + 5;
vector<int> comp[10][10];
vector<pair<int, int> > adj[MAXN];
vector<int> par[MAXN], ord[MAXN];
vector<pair<int, int> > ehh[10][10];
bool saw[10][10];
int perm[MAXN];
int mark[MAXN];
int deg[MAXN];
int n, m, k, ans;
void rec(int p, int good = 0) {
  if (p == k + 1) {
    ans += (good == n);
    return;
  }
  for (int i = 0; i < p; ++i) {
    bool can = 1;
    for (auto it : ehh[p][i]) {
      if (perm[it.first] == it.second) {
        can = 0;
        break;
      }
    }
    if (can) {
      good += comp[p][i].size();
      perm[p] = i;
      rec(p + 1, good);
      good -= comp[p][i].size();
    }
  }
}
void solve() {
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    adj[u].emplace_back(w, v);
    par[v].push_back(u);
    ++deg[u];
  }
  for (int i = 1; i <= n; ++i) {
    sort((adj[i]).begin(), (adj[i]).end());
    for (auto it : adj[i]) {
      ord[i].push_back(it.second);
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (auto j : par[i]) {
      saw[deg[j]][find((ord[j]).begin(), (ord[j]).end(), i) - ord[j].begin()] =
          1;
    }
    vector<pair<int, int> > kek;
    for (int a = 1; a <= k; ++a) {
      vector<pair<int, int> > cur;
      for (int b = 0; b < a; ++b) {
        if (saw[a][b]) {
          cur.emplace_back(a, b);
          saw[a][b] = 0;
          comp[a][b].push_back(i);
        }
      }
      for (pair<int, int> prv : kek) {
        for (pair<int, int> me : cur) {
          ehh[me.first][me.second].push_back(prv);
        }
      }
      for (pair<int, int> me : cur) {
        kek.push_back(me);
      }
    }
  }
  rec(1);
  printf("%d\n", ans);
}
int main() {
  int tt = 1;
  while (tt--) {
    solve();
  }
  return 0;
}
