#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200100;
bool ok[10][9];
bitset<MAXN> results[10][9];
unordered_map<bitset<MAXN>, int> m1;
unordered_map<bitset<MAXN>, int> m2;
bitset<MAXN> curmask;
void recurse(int i, int j) {
  if (i == j) {
    m1[curmask]++;
    return;
  }
  for (int c = 0; c < i; c++) {
    if (ok[i][c]) {
      curmask ^= results[i][c];
      recurse(i + 1, j);
      curmask ^= results[i][c];
    }
  }
}
vector<pair<int, int> > adj[MAXN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    --u;
    --v;
    adj[u].push_back(make_pair(w, v));
  }
  for (int i = 1; i <= k; i++) {
    for (int j = 0; j < i; j++) {
      ok[i][j] = true;
    }
  }
  for (int i = 0; i < m; i++) {
    sort(adj[i].begin(), adj[i].end());
    int deg = adj[i].size();
    for (int j = 0; j < deg; j++) {
      if (results[deg][j].test(adj[i][j].second)) {
        ok[deg][j] = false;
      } else {
        results[deg][j].set(adj[i][j].second);
      }
    }
  }
  curmask.reset();
  int k1 = max(1, k - 3);
  recurse(1, k1);
  curmask.reset();
  swap(m1, m2);
  recurse(k1, k + 1);
  int ans = 0;
  bitset<MAXN> t;
  bitset<MAXN> complete;
  complete.reset();
  for (int i = 0; i < n; i++) {
    complete.set(i);
  }
  for (auto& it : m1) {
    t = it.first;
    t ^= complete;
    auto it2 = m2.find(t);
    if (it2 != m2.end()) {
      ans += it.second * it2->second;
    }
  }
  cout << ans << endl;
}
