#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1},
          dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T &a, U b) {
  return a < b ? (a = b, true) : false;
}
template <typename T, typename U>
inline bool chmin(T &a, U b) {
  return a > b ? (a = b, true) : false;
}
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;
int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> graph(n);
  vector<vector<pair<int, int>>> rev(n);
  while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    --u;
    --v;
    graph[u].emplace_back(w);
    rev[v].emplace_back(u, w);
  }
  for (int i = (0); i < (n); ++i) sort((graph[i]).begin(), (graph[i]).end());
  vector<vector<ll>> ng(k);
  vector<vector<int>> has(k), idx(k);
  for (int i = (0); i < (k); ++i) ng[i].resize(i + 1, 0);
  for (int i = (0); i < (k); ++i) has[i].resize(i + 1, 0);
  for (int i = (0); i < (k); ++i) idx[i].resize(i + 1, 0);
  int tmp = 0;
  for (int i = (0); i < (k); ++i)
    for (int j = (0); j < (i + 1); ++j) idx[i][j] = tmp++;
  for (int i = (0); i < (n); ++i) {
    if (rev[i].empty()) {
      cout << 0 << '\n';
      return 0;
    }
    vector<pair<int, int>> es;
    for (auto [e, w] : rev[i]) {
      int nth = lower_bound((graph[e]).begin(), (graph[e]).end(), w) -
                graph[e].begin();
      es.emplace_back(graph[e].size() - 1, nth);
    }
    sort((es).begin(), (es).end());
    es.erase(unique((es).begin(), (es).end()), es.end());
    reverse((es).begin(), (es).end());
    ll b = 0;
    for (auto [deg, nth] : es) {
      ng[deg][nth] |= b;
      ++has[deg][nth];
      b |= 1LL << idx[deg][nth];
    }
  }
  int ans = 0;
  function<void(int, ll, int)> dfs = [&](int c, ll ban, int have) {
    if (c == k) {
      ans += have == n;
      return;
    }
    for (int i = (0); i < (c + 1); ++i) {
      if (ban >> idx[c][i] & 1) continue;
      dfs(c + 1, ban | ng[c][i], have + has[c][i]);
    }
  };
  dfs(0, 0, 0);
  cout << ans << '\n';
  return 0;
}
