#include <bits/stdc++.h>
using namespace std;
const long long maxn = 2e5 + 7;
struct Node {
  long long to, weight;
};
vector<Node> field[maxn];
vector<long long> sum[10];
vector<long long> hash1[10], hash2[10];
long long n, m, k;
long long ans = 0;
long long tar1, tar2;
bool cmp(Node a, Node b) { return a.weight < b.weight; }
void dfs(long long deep, long long tot1, long long tot2) {
  if (deep == k + 1) {
    if (tot1 == tar1 && tot2 == tar2) ans++;
    return;
  }
  for (long long i = 0; i < deep; i++) {
    dfs(deep + 1, tot1 + hash1[deep][i], tot2 + hash2[deep][i]);
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m >> k;
  for (long long i = 0; i < m; i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    field[u].push_back({v, w});
  }
  for (long long i = 1; i <= n; i++) {
    tar1 += i * i * i;
    tar2 += i * i;
    sort(field[i].begin(), field[i].end(), cmp);
    sum[field[i].size()].push_back(i);
  }
  for (long long i = 1; i <= k; i++) {
    for (long long j = 0; j < i; j++) {
      unordered_map<long long, long long> M;
      long long temp1 = 0, temp2 = 0;
      for (auto &x : sum[i]) {
        long long to = field[x][j].to;
        temp1 += to * to * to;
        temp2 += to * to;
      }
      hash1[i].push_back(temp1);
      hash2[i].push_back(temp2);
    }
  }
  dfs(1, 0, 0);
  cout << ans << endl;
}
