1394B

int n,m,k,ans;
vpi adj[MX];
map<pi,int> bad[MX];

int BAD[500][500];
int hsh(pi p) { return 10*p.f+p.s; }

vpi st;
void dfs(int x) {
    if (x == k+1) {
        ans ++;
        return;
    }
    F0R(i,x) {
        pi p = {x,i};
        st.pb(p);
        bool oops = 0;
        trav(t,st) if (BAD[hsh(p)][hsh(t)]) oops = 1;
        if (!oops) {
            dfs(x+1);
        }
        st.pop_back();
    }
}

int main() {
    setIO(); re(n,m,k);
    F0R(i,m) {
        int u,v,w; re(u,v,w);
        adj[u].pb({w,v});
    }
    FOR(i,1,n+1) {
        sort(all(adj[i]));
        F0R(j,sz(adj[i])) bad[adj[i][j].s][{sz(adj[i]),j}] ++;
    }
    FOR(i,1,n+1) {
        trav(a,bad[i]) trav(b,bad[i]) if (a.f != b.f) {
            BAD[hsh(a.f)][hsh(b.f)] = 1;
        } else if (a.s > 1) {
            BAD[hsh(a.f)][hsh(b.f)] = 1;
        }
    }
    dfs(1);
    ps(ans);
    // you should actually read the stuff at the bottom
}