#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
constexpr ll lim = 10;
bool forbidden[lim][lim][lim][lim];
int state[lim];
ll res = 0;
void check(ll k, ll pos = 1) {
  if (pos > k) {
    for (ll i = 1; i <= k; i++) {
      for (ll j = i; j <= k; j++) {
        if (forbidden[i][state[i]][j][state[j]]) return;
      }
    }
    res++;
  } else {
    for (ll i = 0; i < pos; i++) {
      state[pos] = i;
      check(k, pos + 1);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n, m, k;
  cin >> n >> m >> k;
  vector<vector<pair<ll, ll>>> adj(n);
  for (ll i = 0; i < m; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    adj[a].push_back({c, b});
  }
  vector<map<pair<ll, ll>, ll>> rev(n);
  for (ll i = 0; i < n; i++) {
    sort(begin(adj[i]), end(adj[i]));
    for (ll j = 0; j < (ll)(adj[i]).size(); j++) {
      ll to = adj[i][j].second;
      rev[to][{(ll)(adj[i]).size(), j}]++;
    }
  }
  for (ll i = 0; i < n; i++) {
    for (auto e : rev[i]) {
      if (e.second > 1)
        forbidden[e.first.first][e.first.second][e.first.first]
                 [e.first.second] = true;
      for (auto e2 : rev[i]) {
        if (e2.first == e.first) continue;
        forbidden[e.first.first][e.first.second][e2.first.first]
                 [e2.first.second] = true;
      }
    }
  }
  check(k);
  cout << res << endl;
}
