#include #include #include using namespace std; using ll = long long; using P = pair; int main(void){ int n, m, k; cin >> n >> m >> k; vector> to(n+1); for(int i=0; i> a >> b >> c; a--, b--; to[a].emplace_back(b, c); swap(a, b); to[a].emplace_back(b, c); } for(int i=0; i d(k); for(int i=1; i> d[i]; vector dp(n+1); dp[n]=true; for(int i=0; i old(n); swap(old, dp); for(int j=0; j<=n; j++)if(old[j]){ for(auto [v, c]:to[j])if(d[i]==c){ dp[v]=true; } } } vector ans; for(int i=0; i