#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int visited[10][10];
int n, m, K;
vector<pair<int, int>> blockat[10][10];
vector<pair<int, int>> v1[MAXN];
bool blocked[MAXN][10][10];
int solve(int x) {
  if (x == (K + 1)) {
    return 1;
  }
  int ans = 0;
  for (int i = 1; i <= x; i++) {
    if (visited[x][i]) {
      continue;
    }
    for (auto y : blockat[x][i]) {
      visited[y.first][y.second]++;
    }
    ans += solve(x + 1);
    for (auto y : blockat[x][i]) {
      visited[y.first][y.second]--;
    }
  }
  return ans;
}
int main() {
  cin >> n >> m >> K;
  for (int i = 1; i <= m; i++) {
    int x, y, w;
    cin >> x >> y >> w;
    v1[x].push_back(make_pair(w, y));
  }
  for (int i = 1; i <= n; i++) {
    sort(v1[i].begin(), v1[i].end());
    for (int j = 0; j < v1[i].size(); j++) {
      if (blocked[v1[i][j].second][(int)v1[i].size()][j + 1]) {
        visited[(int)v1[i].size()][j + 1]++;
      }
      blocked[v1[i][j].second][(int)v1[i].size()][j + 1] = true;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= K; j++) {
      for (int k = 1; k < j; k++) {
        for (int x = 1; x <= j; x++) {
          for (int y = 1; y <= k; y++) {
            if (blocked[i][j][x] && blocked[i][k][y]) {
              blockat[k][y].push_back(make_pair(j, x));
            }
          }
        }
      }
    }
  }
  cout << solve(1) << endl;
}
