#include <bits/stdc++.h>
using namespace std;
int hashPair(pair<int, int> pr) { return 10 * pr.first + pr.second; }
int n, m, k;
bool bad[100][100];
vector<int> neighbours[200001];
map<pair<int, int>, int> inEdges[200001];
vector<pair<int, int> > st;
int dfs(int depth) {
  if (depth == k + 1) return 1;
  int ans = 0;
  for (int choice = 0; choice < depth; ++choice) {
    pair<int, int> p = {depth, choice};
    st.push_back(p);
    bool possible = true;
    for (auto &q : st) {
      if (bad[hashPair(p)][hashPair(q)]) {
        possible = false;
        break;
      }
    }
    if (possible) ans += dfs(depth + 1);
    st.pop_back();
  }
  return ans;
}
int main() {
  cin >> n >> m >> k;
  vector<pair<int, int> > edges(m);
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    edges[w - 1] = {u, v};
  }
  for (pair<int, int> edge : edges)
    neighbours[edge.first].push_back(edge.second);
  for (int i = 1; i <= n; ++i) {
    int outDegree = neighbours[i].size();
    for (int j = 0; j < neighbours[i].size(); ++j)
      ++inEdges[neighbours[i][j]][{outDegree, j}];
  }
  for (int i = 1; i <= n; ++i) {
    for (auto a : inEdges[i])
      for (auto b : inEdges[i]) {
        if (a.first != b.first || a.second > 1)
          bad[hashPair(a.first)][hashPair(b.first)] = true;
      }
  }
  cout << dfs(1) << endl;
  return 0;
}
