#include <bits/stdc++.h>
using namespace std;
struct Info {
  int v, w;
} Edge[200007];
long long const mod[3] = {1000000007, 1226959, 998244353};
int n, m, k, c[200007], e[200007][10], randnum[200007][3], hashans[3];
int f[10][10][3];
bool cmp(int a, int b) { return Edge[a].w < Edge[b].w; }
int ans;
void dfs(int ste, int s0, int s1, int s2) {
  if (ste > k) {
    if (s0 == hashans[0] && s1 == hashans[1] && s2 == hashans[2]) ++ans;
    return;
  }
  for (int i = 1; i <= ste; ++i)
    dfs(ste + 1, 1ll * s0 * f[ste][i][0] % mod[0],
        1ll * s1 * f[ste][i][1] % mod[1], (s2 + f[ste][i][2]) % mod[2]);
}
int main() {
  srand((unsigned)time(NULL));
  scanf("%d%d%d", &n, &m, &k);
  hashans[0] = hashans[1] = 1;
  for (int i = 1; i <= n; ++i) {
    randnum[i][0] = abs(rand() % mod[0]), randnum[i][1] = abs(rand() % mod[1]);
    randnum[i][2] = abs(rand() % mod[2]);
    hashans[0] = 1ll * hashans[0] * randnum[i][0] % mod[0];
    hashans[1] = 1ll * hashans[1] * randnum[i][1] % mod[1];
    hashans[2] = (hashans[2] + randnum[i][2]) % mod[2];
  }
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    Edge[i] = (Info){v, w};
    e[u][++c[u]] = i;
  }
  for (int i = 1; i <= k; ++i)
    for (int j = 1; j <= i; ++j) f[i][j][0] = f[i][j][1] = 1;
  for (int i = 1; i <= n; ++i) {
    sort(e[i] + 1, e[i] + c[i] + 1, cmp);
    for (int j = 1; j <= c[i]; ++j) {
      f[c[i]][j][0] =
          1ll * f[c[i]][j][0] * randnum[Edge[e[i][j]].v][0] % mod[0];
      f[c[i]][j][1] =
          1ll * f[c[i]][j][1] * randnum[Edge[e[i][j]].v][1] % mod[1];
      f[c[i]][j][2] = (f[c[i]][j][2] + randnum[Edge[e[i][j]].v][2]) % mod[2];
    }
  }
  dfs(1, 1, 1, 0);
  printf("%d\n", ans);
  return 0;
}
