MOD = 10 ** 9 + 7
N, M, K = map(int, input().split())
PQC = [list(map(int, input().split())) for _ in range(M)]
dp = [([1] + [0] * K) for _ in range(301)]
for i in range(N - 1):
    dp2 = [[0] * (K + 1) for _ in range(301)]
    for p, q, c in PQC:
        for i in range(K - c + 1):
            dp2[q][i + c] += dp[p][i]
    dp = dp2
ans = 0
for i in range(301):
    ans += dp[i][-1]
print(ans)