#include <bits/stdc++.h>
using namespace std;
const int mxn = 200000, mxk = 9;
int n, m, k;
int a[mxn][mxk][mxk];
int vis[mxk][mxk];
vector<pair<int, int> > g[mxn];
vector<pair<int, int> > gr[mxk][mxk];
int sol(int x) {
  if (x == k) return 1;
  int ret = 0;
  for (int i = 0; i <= x; i++) {
    if (vis[x][i]) continue;
    for (pair<int, int> j : gr[x][i]) vis[j.first][j.second]++;
    ret += sol(x + 1);
    for (pair<int, int> j : gr[x][i]) vis[j.first][j.second]--;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    g[--u].push_back({w, --v});
  }
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end());
    int l = g[i].size();
    for (int j = 0; j < l; j++) {
      a[g[i][j].second][l - 1][j]++;
    }
  }
  for (int i = 0; i < n; i++)
    for (int j1 = 0; j1 < k; j1++)
      for (int j2 = 0; j2 <= j1; j2++) {
        vis[j1][j2] += a[i][j1][j2] >= 2;
        for (int l1 = 0; l1 < j1; l1++)
          for (int l2 = 0; l2 <= l1; l2++) {
            if (a[i][j1][j2] && a[i][l1][l2]) {
              gr[l1][l2].push_back({j1, j2});
            }
          }
      }
  cout << sol(0) << '\n';
  return 0;
}
