#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using vec = vector<T>;
template <typename T>
using Prior = priority_queue<T>;
template <typename T>
using prior = priority_queue<T, vec<T>, greater<T>>;
const int INF = 1e9 + 1;
const ll LLINF = (ll)4 * 1e18;
const ll MOD = 1e9 + 7;
const double PI = 3.14159265358;
const double EPS = 1e-8;
const int xx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int yy[8] = {1, 0, -1, 0, 1, -1, -1, 1};
template <typename T>
void dbg(T x) {
  cerr << x << '\n';
}
template <typename T, typename... A>
void dbg(T x, A... y) {
  cerr << x << ", ";
  dbg(y...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
void amax(T &a, T b) {
  if (a < b) a = b;
}
template <typename T>
void amin(T &a, T b) {
  if (a > b) a = b;
}
void pmod(ll &a, ll b) { a = (a + b) % MOD; }
void mmod(ll &a, ll b) { a = (a - b + MOD) % MOD; }
void tmod(ll &a, ll b) { a = (a * b) % MOD; }
void UNI(vec<int> &v) {
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
}
int getint() {
  int ret;
  cin >> ret;
  return ret;
}
ll POW(ll a, ll b) {
  ll res = 1;
  do {
    if (b % 2) tmod(res, a);
    tmod(a, a);
  } while (b >>= 1);
  return res;
}
ll getll() {
  ll ret;
  cin >> ret;
  return ret;
}
const int MXN = 200000;
const int N = MXN + 10;
vec<pii> g[N];
int c[10], d;
bool add() {
  int k = d;
  c[k]++;
  while (k > 1 && c[k] > k) {
    c[k] = 1;
    c[k - 1]++;
    k--;
  }
  return c[1] == 1;
}
void solve() {
  int n, m, ipa, ipb, ipv;
  cin >> n >> m >> d;
  for (int i = 0; i < (m); i++) {
    cin >> ipa >> ipb >> ipv;
    g[ipa].emplace_back(ipb, ipv);
  }
  for (int i = 1; i <= (n); i++)
    sort(g[i].begin(), g[i].end(),
         [](pii a, pii b) { return a.second < b.second; });
  unordered_set<int> st[100], a, b;
  vec<int> v[10];
  bool flag;
  for (int i = 1; i <= (n); i++) v[((int)g[i].size())].emplace_back(i);
  for (int i = 1; i <= (d); i++)
    for (int j = 1; j <= (i); j++) {
      a.clear();
      flag = false;
      for (auto u : v[i]) {
        int k = g[u][j - 1].first;
        if (a.count(k)) {
          flag = true;
          break;
        } else
          a.insert(k);
      }
      if (flag) continue;
      st[i * 10 + j].insert(i * 10 + j);
      for (int u = (i + 1); u <= (d); u++)
        for (int o = 1; o <= (u); o++) {
          b.clear();
          flag = false;
          for (auto p : v[u]) {
            int k = g[p][o - 1].first;
            if (a.count(k) || b.count(k)) {
              flag = true;
              break;
            } else
              b.insert(k);
          }
          if (!flag) {
            st[i * 10 + j].insert(u * 10 + o);
            st[u * 10 + o].insert(u * 10 + o);
          }
        }
    }
  int ans = 0;
  for (int i = 1; i <= (d - 1); i++) c[i] = 1;
  while (add()) {
    flag = true;
    for (int i = 1; i <= (d); i++) {
      if (!st[i * 10 + c[i]].count(i * 10 + c[i])) {
        flag = false;
        break;
      }
      for (int j = (i + 1); j <= (d); j++)
        if (!st[i * 10 + c[i]].count(j * 10 + c[j])) {
          flag = false;
          break;
        }
      if (!flag) break;
    }
    if (flag) ans++;
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T = 1;
  while (T--) {
    solve();
  }
}
