#include <bits/stdc++.h>
using namespace std;
mt19937 gen(time(NULL));
struct Edge {
  int to;
  int weight;
  Edge(const int to_, const int weight_) : to(to_), weight(weight_) {}
};
bool operator<(const Edge& left, const Edge& right) {
  return left.weight < right.weight;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<Edge>> adj(n);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u - 1].push_back(Edge(v - 1, w));
  }
  vector<int> outDegree(n);
  for (int i = 0; i < n; i++) {
    outDegree[i] = (int)(adj[i].size());
    sort(adj[i].begin(), adj[i].end());
  }
  vector<long long> hashs(n);
  int total = 0;
  for (int i = 0; i < n; i++) {
    hashs[i] = uniform_int_distribution<int>(1, INT_MAX)(gen);
    total ^= hashs[i];
  }
  vector<vector<long long>> subSets(k + 1, vector<long long>(k + 1));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < outDegree[i]; j++)
      subSets[outDegree[i]][j] ^= hashs[adj[i][j].to];
  int res = 0;
  function<void(int, int)> go = [&](long long curHash, int curDeg) {
    if (curDeg > k) {
      if (curHash == total) res++;
      return;
    }
    for (int nxt = 0; nxt < curDeg; nxt++)
      go(curHash ^ subSets[curDeg][nxt], curDeg + 1);
  };
  go(0LL, 1);
  cout << res << "\n";
  return 0;
}
