#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
const long long MOD = 1e9 + 7;
const long long INF = 2e9;
const int fullmask = (1 << 10) - 1;
long long fpow(int n, int p) {
  if (!p) return 1;
  if (p == 1) return n;
  long long tmp = fpow(n, p / 2);
  if (p & 1) return tmp * tmp % MOD * n % MOD;
  return tmp * tmp % MOD;
}
long long Hash[10][10];
int k, n, m, u, v, w, c[10], ans;
vector<pair<int, int> > g[N];
void solve(int id) {
  if (id > k) {
    long long op = 0;
    for (int i = 1; i <= k; i++) op += Hash[i][c[i]], op %= MOD;
    if (op == ((fpow(2, n + 1) - 2 + MOD) % MOD)) ans++;
    return;
  }
  for (int i = 1; i <= id; i++) {
    c[id] = i;
    solve(id + 1);
  }
}
void process() {
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v >> w;
    g[u].push_back(pair<int, int>(w, v));
  }
  for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
  for (int i = 1; i <= n; i++) {
    int deg = g[i].size();
    for (int j = 1; j <= deg; j++) {
      int v = g[i][j - 1].second;
      Hash[deg][j] += fpow(2, v);
      Hash[deg][j] %= MOD;
    }
  }
  solve(1);
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  process();
}
