const int mod[3]={998244353,1004535809,1<<30},MAXN=2e5+5,MAXK=10,Base=32767;
struct Hash_num{
	int h[3];
	Hash_num(LL seed=0){_for(i,0,3)h[i]=seed%mod[i];}
	Hash_num operator + (const Hash_num &b)const{
		Hash_num c;
		c.h[0]=(h[0]+b.h[0])%mod[0];
		c.h[1]=1LL*h[1]*b.h[1]%mod[1];
		c.h[2]=h[2]^b.h[2];
		return c;
	}
	void operator += (const Hash_num &b){
		h[0]=(h[0]+b.h[0])%mod[0];
		h[1]=1LL*h[1]*b.h[1]%mod[1];
		h[2]=h[2]^b.h[2];
	}
	bool operator == (const Hash_num &b)const{
		_for(i,0,3)if(h[i]!=b.h[i])return false;
		return true;
	}
};
Hash_num a[MAXN],s[MAXK][MAXK],t;
LL get_rand(){return 1LL*rand()*Base*Base+1LL*rand()*Base+rand();}
struct Edge{
	int to,next;
}edge[MAXN<<1];
int deg[MAXN],head[MAXN],edge_cnt,k,ans;
pair<int,int> temp[MAXN];
void Insert(int u,int v){
	edge[++edge_cnt]=Edge{v,head[u]};
	head[u]=edge_cnt;
}
void dfs(int pos,Hash_num cur){
	if(pos>k){
		if(cur==t)ans++;
		return;
	}
	_rep(i,1,pos)
	dfs(pos+1,cur+s[pos][i]);
}
int main()
{
	srand(time(NULL));
	int n=read_int(),m=read_int(),u,v,w;
	k=read_int();
	_rep(i,1,m){
		u=read_int(),v=read_int(),w=read_int();
		temp[w]=make_pair(u,v);
		deg[u]++;
	}
	for(int i=m;i;i--)
	Insert(temp[i].first,temp[i].second);
	_rep(i,1,n)a[i]=Hash_num(get_rand()),t+=a[i];
	_rep(u,1,n){
		for(int i=head[u],j=1;i;i=edge[i].next,j++){
			int v=edge[i].to;
			s[deg[u]][j]+=a[v];
		}
	}
	dfs(1,Hash_num());
	enter(ans);
	return 0;
}