#include <bits/stdc++.h>
using namespace std;
const int maxn = 200200;
int n, k, m;
vector<pair<int, int> > g[maxn];
set<pair<int, int> > st[maxn];
int ans;
bool bad[12][12];
bool dab[12][12][12][12];
int c[12];
void addin(int v, int z, int f) {
  if (st[v].count({z, f})) {
    bad[z][f] = true;
  } else {
    for (auto it : st[v])
      dab[it.first][it.second][z][f] = dab[z][f][it.first][it.second] = true;
    st[v].insert({z, f});
  }
}
void bt(int i) {
  if (i > k) {
    ans++;
    return;
  }
  for (int d = 0; d < i; d++) {
    if (bad[i][d]) continue;
    bool bd = false;
    for (int j = 1; j < i; j++)
      if (dab[j][c[j]][i][d]) {
        bd = true;
        break;
      }
    if (bd) continue;
    c[i] = d;
    bt(i + 1);
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int v, u, w;
    cin >> v >> u >> w;
    v--, u--;
    g[v].push_back({w, u});
  }
  for (int v = 0; v < n; v++) {
    if (!g[v].size()) {
      cout << 0 << endl;
      return 0;
    }
    sort(g[v].begin(), g[v].end());
    for (int i = 0; i < g[v].size(); i++) addin(g[v][i].second, g[v].size(), i);
  }
  bt(1);
  cout << ans << endl;
  return 0;
}
