#include #include #include #include using namespace std; int main(){ int N, M, K, a, b; long long c, d; cin >> N >> M >> K; vector> abc(M); for(int i=0; i> a >> b >> c; abc[i] = make_tuple(a, b, c); } bool dp[K+1][N+1]; for(int i=0; i> d; for(int j=0; j(abc[j])){ dp[i][get<0>(abc[j])] = true; dp[i][get<1>(abc[j])] = true; } }else{ if(d==get<2>(abc[j])){ if(dp[i-1][get<0>(abc[j])]) dp[i][get<1>(abc[j])] = true; if(dp[i-1][get<1>(abc[j])]) dp[i][get<0>(abc[j])] = true; } } } } cout << accumulate(dp[K-1], dp[K-1]+N+1, 0) << endl; for(int j=1; j