#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const long long mod = 1e9 + 7;
struct node {
  int to, val;
  bool operator<(const node& n) const { return val < n.val; }
};
vector<node> G[maxn];
int n, m, k, ans, c[12];
long long val[12][12], num[maxn], Sum;
bool check() {
  long long sum = 0;
  for (int i = 1; i <= k; i++) sum += val[i][c[i]];
  return sum == Sum;
}
void dfs(int now) {
  if (now > k) {
    if (check()) ans++;
    return;
  }
  for (int i = 1; i <= now; i++) {
    c[now] = i;
    dfs(now + 1);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  srand(time(0));
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int u, v, val;
    cin >> u >> v >> val;
    G[u].push_back({v, val});
  }
  for (int i = 1; i <= n; i++) num[i] = rand() % mod, Sum += num[i];
  for (int i = 1; i <= n; i++) {
    int sz = G[i].size();
    sort(G[i].begin(), G[i].end());
    for (int j = 0; j < sz; j++) val[sz][j + 1] += num[G[i][j].to];
  }
  dfs(1);
  cout << ans << endl;
  return 0;
}
