#include <bits/stdc++.h>
using namespace std;
const int N = 2E5 + 10;
const long long MOD = 1E9 + 7;
int n, m, k;
int s[N][2];
vector<int> G[N];
long long sum[10][10];
long long cnt, rd[N], ans[10], ct = 0;
void check() {
  long long v = 0;
  for (int i = 1; i <= k; i++) v += sum[i][ans[i]];
  if (v == cnt) ct++;
  return;
}
void dfs(int d) {
  if (d > k) return check();
  for (ans[d] = 1; ans[d] <= d; ans[d]++) dfs(d + 1);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    s[w][0] = u, s[w][1] = v;
  }
  for (int i = 1; i <= m; i++) G[s[i][0]].push_back(s[i][1]);
  for (int i = 1; i <= n; i++) rd[i] = rand() % MOD, cnt += rd[i];
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= G[i].size() - 1; j++)
      sum[G[i].size()][j + 1] += rd[G[i][j]];
  dfs(1);
  cout << ct;
}
