#include <bits/stdc++.h>
const int LG = 21;
const int N = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;
using namespace std;
int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Yes[2] = {"No", "Yes"};
string YES[2] = {"NO", "YES"};
long long inq(long long x, long long y) {
  if (!y) return 1 % MOD;
  long long l = inq(x, y / 2);
  if (y % 2) return l * l % MOD * x % MOD;
  return l * l % MOD;
}
long long rev(long long x) { return inq(x, MOD - 2); }
bool __precomputed_combinatorics = 0;
vector<long long> __fact, __ufact, __rev;
void __precompute_combinatorics() {
  __precomputed_combinatorics = 1;
  __fact.resize(N);
  __ufact.resize(N);
  __rev.resize(N);
  __rev[1] = 1;
  for (int i = 2; i < N; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
  __fact[0] = 1, __ufact[0] = 1;
  for (int i = 1; i < N; i++)
    __fact[i] = __fact[i - 1] * i % MOD,
    __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}
long long fact(int x) {
  if (!__precomputed_combinatorics) __precompute_combinatorics();
  return __fact[x];
}
long long cnk(int n, int k) {
  if (k < 0 || k > n) return 0;
  if (!__precomputed_combinatorics) __precompute_combinatorics();
  return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}
int Root(int x, vector<int> &root) {
  if (x == root[x]) return x;
  return root[x] = Root(root[x], root);
}
void Merge(int v, int u, vector<int> &root, vector<int> &sz) {
  v = Root(v, root), u = Root(u, root);
  if (v == u) return;
  if (sz[v] < sz[u]) {
    sz[u] += sz[v];
    root[v] = u;
  } else {
    sz[v] += sz[u];
    root[u] = v;
  }
}
int ok(int x, int n) { return 0 <= x && x < n; }
void bfs(int v, vector<int> &dist, vector<vector<int> > &graph) {
  fill((dist).begin(), (dist).end(), -1);
  dist[v] = 0;
  vector<int> q = {v};
  for (int i = 0; i < q.size(); i++) {
    for (auto u : graph[q[i]]) {
      if (dist[u] == -1) {
        dist[u] = dist[q[i]] + 1;
        q.push_back(u);
      }
    }
  }
}
vector<int> z_func(string &s) {
  vector<int> z(s.size());
  z[0] = s.size();
  int L = 0, R = 0;
  for (int i = 1; i < s.size(); i++) {
    z[i] = max(0, min(z[i - L], R - i));
    while (i + z[i] < s.size() && s[i + z[i]] == s[z[i]]) z[i]++;
    if (i + z[i] > R) {
      R = i + z[i];
      L = i;
    }
  }
  return z;
}
vector<int> p_func(string &s) {
  vector<int> p(s.size());
  for (int i = 1; i < s.size(); i++) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) j++;
    p[i] = j;
  }
  return p;
}
vector<int> d1_func(string &s) {
  vector<int> d1(s.size());
  int L = 0, R = -1;
  for (int i = 0; i < s.size(); i++) {
    int k = 0;
    if (i <= R) k = min(R - i + 1, d1[R - i + L]);
    while (i + k < s.size() && i - k >= 0 && s[i - k] == s[i + k]) k++;
    d1[i] = k--;
    if (i + k > R) {
      L = i - k;
      R = i + k;
    }
  }
  return d1;
}
vector<int> d2_func(string &s) {
  vector<int> d2(s.size());
  int L = 0, R = -1;
  for (int i = 1; i < s.size(); i++) {
    int k = 0;
    if (i <= R) k = min(R - i + 1, d2[R - i + L + 1]);
    while (i + k < s.size() && i - k - 1 >= 0 && s[i - k - 1] == s[i + k]) k++;
    d2[i] = k--;
    if (i + k > R) {
      L = i - k - 1;
      R = i + k;
    }
  }
  return d2;
}
long long log10(long long x) {
  if (x < 10) return 1;
  return 1 + log10(x / 10);
}
long long ds(long long x) {
  if (x < 10) return x;
  return x % 10 + ds(x / 10);
}
double sqr(double x) { return x * x; }
bool in(int bit, int mask) { return (mask & (1 << bit)) > 0; }
void Del(vector<int> &v, int pos) {
  swap(v[pos], v[v.size() - 1]);
  v.pop_back();
}
long long g(vector<long long> &p, int pos) {
  if (ok(pos, p.size())) return p[pos];
  if (pos < 0 || p.size() == 0) return 0;
  return p.back();
}
int g(vector<int> &p, int pos) {
  if (ok(pos, p.size())) return p[pos];
  if (pos < 0 || p.size() == 0) return 0;
  return p.back();
}
int n, m, k;
vector<pair<int, int> > go[N];
int mat[N][10][10];
vector<pair<int, int> > block[10][10];
int blocks[10][10][10][10];
int BLOCK[10][10];
int allow[10][10];
int ans;
void rec(int z) {
  if (z == k) {
    ans++;
    return;
  }
  for (int sel = 0; sel <= z; sel++) {
    if (BLOCK[z][sel] == 0 && allow[z][sel] == 0) {
      for (auto go : block[z][sel]) allow[go.first][go.second]++;
      rec(z + 1);
      for (auto go : block[z][sel]) allow[go.first][go.second]--;
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  for (int(i) = 0; (i) != (m); (i)++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    go[a].push_back({c, b});
  }
  for (int(i) = 0; (i) != (n); (i)++) {
    sort((go[i]).begin(), (go[i]).end());
  }
  for (int(i) = 0; (i) != (n); (i)++) {
    for (int j = 0; j < go[i].size(); j++) {
      int v = go[i][j].second;
      mat[v][go[i].size() - 1][j]++;
    }
  }
  for (int(v) = 0; (v) != (n); (v)++) {
    vector<pair<int, int> > s;
    for (int i = 0; i < k; i++) {
      for (int j = 0; j <= i; j++) {
        if (mat[v][i][j] > 1) BLOCK[i][j] = 1;
        if (mat[v][i][j] == 1) s.push_back({i, j});
      }
    }
    for (int i = 0; i < s.size(); i++) {
      for (int j = i + 1; j < s.size(); j++) {
        blocks[s[i].first][s[i].second][s[j].first][s[j].second] = 1;
      }
    }
  }
  for (int i1 = 0; i1 < k; i1++) {
    for (int j1 = 0; j1 <= i1; j1++) {
      for (int i2 = 0; i2 < k; i2++) {
        for (int j2 = 0; j2 < k; j2++) {
          if (blocks[i1][j1][i2][j2]) block[i1][j1].push_back({i2, j2});
        }
      }
    }
  }
  rec(0);
  cout << ans;
}
