#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int ans, n, m, k, a[12];
struct Edge {
  int to, t;
  Edge() { to = t = 0; }
  Edge(int _to, int _t) {
    to = _to;
    t = _t;
  }
  bool operator<(const Edge &z) const { return t < z.t; }
};
vector<Edge> vec[N];
int d[N][12][12];
bool vis[12][12][12][12];
inline void dfs(int x) {
  if (k + 1 == x) {
    for (int i = 1; i <= k; i++)
      for (int j = 1; j <= k; j++)
        if (vis[i][a[i]][j][a[j]]) return;
    ans++;
    return;
  }
  for (int i = 1; i <= x; i++) a[x] = i, dfs(x + 1);
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  int s, e, t;
  for (int i = 1; i <= m; i++)
    scanf("%d%d%d", &s, &e, &t), vec[s].push_back(Edge(e, t));
  for (int i = 1; i <= n; i++) {
    sort(vec[i].begin(), vec[i].end());
    for (int j = 0; j < vec[i].size(); j++)
      d[vec[i][j].to][vec[i].size()][j + 1]++;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < vec[i].size(); j++)
      for (int t = 1; t <= k; t++)
        for (int l = 1; l <= k; l++)
          if (d[vec[i][j].to][t][l]) {
            if (t ^ vec[i].size())
              vis[vec[i].size()][j + 1][t][l] = 1;
            else if (d[vec[i][j].to][t][l] > 1)
              vis[vec[i].size()][j + 1][t][l] = 1;
          }
  dfs(1);
  return printf("%d\n", ans), 0;
}
