#include <bits/stdc++.h>
using namespace std;
const long long MOD = (long long)1e9 + 7;
const int SIZE = 2e5 + 5;
const long long INF = 1LL << 60;
const double eps = 1e-4;
const double PI = 3.1415926535897932;
int n, m, k;
int cnt[200009];
vector<pair<int, int> > adj[200009];
int ans = 0;
vector<int> nout[10];
bool fight[10][10][10][10];
void bt(vector<int> d) {
  if (((int)(d).size()) == k) {
    ans++;
    return;
  }
  int j = ((int)(d).size());
  for (int cj = 0; cj < (j + 1); ++cj) {
    bool good = !fight[j + 1][cj][j + 1][cj];
    for (int i = 0; i < (j); ++i) {
      if (fight[i + 1][d[i]][j + 1][cj]) {
        good = 0;
        break;
      }
    }
    if (!good) continue;
    d.push_back(cj);
    bt(d);
    d.pop_back();
  }
}
int main() {
  scanf("%d%d%d", &(n), &(m), &(k));
  for (int i = 0; i < (m); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    adj[a].push_back(make_pair(c, b));
  }
  for (int i = 0; i < (n); ++i) {
    sort((adj[i]).begin(), (adj[i]).end());
    nout[((int)(adj[i]).size())].push_back(i);
  }
  for (int i = 1; i < k + 1; i++) {
    for (int ci = 0; ci < (i); ++ci) {
      bool bad = 0;
      for (int x : nout[i]) {
        if (cnt[adj[x][ci].second] == 1) {
          bad = 1;
          break;
        }
        cnt[adj[x][ci].second]++;
      }
      fight[i][ci][i][ci] = bad;
      for (int x : nout[i]) {
        cnt[adj[x][ci].second] = 0;
      }
      for (int j = (i + 1); j < (k + 1); ++j) {
        for (int cj = 0; cj < (j); ++cj) {
          bool bad = 0;
          for (int x : nout[i]) {
            if (cnt[adj[x][ci].second] == 1) {
              bad = 1;
              break;
            }
            cnt[adj[x][ci].second]++;
          }
          for (int x : nout[j]) {
            if (cnt[adj[x][cj].second] == 1) {
              bad = 1;
              break;
            }
            cnt[adj[x][cj].second]++;
          }
          fight[i][ci][j][cj] = bad;
          for (int x : nout[i]) {
            cnt[adj[x][ci].second] = 0;
          }
          for (int x : nout[j]) {
            cnt[adj[x][cj].second] = 0;
          }
        }
      }
    }
  }
  bt(vector<int>());
  printf("%d", ans);
}
