import sys

def solve(): data = sys.stdin.read().split() n = int(data[0]); m = int(data[1]); d = int(data[2])

# Precompute edge masks: edge[bit][u] = bitmask of neighbors via edge labeled `bit`
edge = [0] * n
edge0 = edge[:]
edge1 = edge[:]

idx = 3
for _ in range(m):
    u = int(data[idx]) - 1
    v = int(data[idx+1]) - 1
    bit = int(data[idx+2])
    if bit == 0:
        edge0[u] |= (1 << v)
        if u != v:
            edge0[v] |= (1 << u)
    else:
        edge1[u] |= (1 << v)
        if u != v:
            edge1[v] |= (1 << u)
    idx += 3

# dp[mask] = bitmask of nodes reachable with binary path `mask`
dp = [0] * (1 << d)
dp[0] = 1  # Start at node 0 (house 1)

# Build DP for each path length
for i in range(d):
    new_dp = [0] * (1 << (i + 2))
    for mask in range(len(dp)):
        if not dp[mask]:
            continue
        nodes = dp[mask]
        # Append 0
        next_nodes0 = 0
        for u in range(n):
            if nodes & (1 << u):
                next_nodes0 |= edge0[u]
        new_dp[mask << 1] |= next_nodes0

        # Append 1
        next_nodes1 = 0
        for u in range(n):
            if nodes & (1 << u):
                next_nodes1 |= edge1[u]
        new_dp[(mask << 1) | 1] |= next_nodes1
    dp = new_dp

# Count distinct masks of length d that are reachable
result = sum(1 for i in range(1 << d) if dp[i])
print(result)

solve()