#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ifstream fin("fart.in"); ofstream fout("fart.out"); int N, M, K; fin >> N >> M >> K; // Store available masks in each city as bitmasks vector cityOffer(N + 1, 0); for (int i = 1; i <= N; i++) { string s; fin >> s; int mask = 0; for (int j = 0; j < K; j++) { if (s[j] == '1') { mask |= (1 << j); } } cityOffer[i] = mask; } // Graph representation: city -> (neighbor, required gases as bitmask) vector>> graph(N + 1); for (int i = 0; i < M; i++) { int u, v; string s; fin >> u >> v >> s; int req = 0; for (int j = 0; j < K; j++) { if (s[j] == '1') { req |= (1 << j); } } graph[u].push_back({v, req}); graph[v].push_back({u, req}); } const int MAX_MASK = 1 << K; const int INF = 1e9; // dp[city][mask] = minimum masks bought to reach city with mask set vector> dp(N + 1, vector(MAX_MASK, INF)); // Priority queue with (cost, city, mask) - using Dijkstra's approach typedef tuple State; priority_queue, greater> pq; // Start at city 1 with no masks dp[1][0] = 0; pq.push({0, 1, 0}); while (!pq.empty()) { auto [cost, city, mask] = pq.top(); pq.pop(); if (cost != dp[city][mask]) continue; // If we've reached city N, output answer immediately if (city == N) { fout << cost << "\n"; return 0; } // Option 1: Buy new masks in the current city int available = cityOffer[city] & (~mask); for (int j = 0; j < K; j++) { if (available & (1 << j)) { int newMask = mask | (1 << j); if (dp[city][newMask] > cost + 1) { dp[city][newMask] = cost + 1; pq.push({cost + 1, city, newMask}); } } } // Option 2: Travel to neighboring cities for (auto &edge : graph[city]) { int nxt = edge.first; int req = edge.second; if ((mask & req) == req) { if (dp[nxt][mask] > cost) { dp[nxt][mask] = cost; pq.push({cost, nxt, mask}); } } } } // If no valid path to city N, print -1 int ans = INF; for (int m = 0; m < MAX_MASK; m++) { ans = min(ans, dp[N][m]); } fout << (ans == INF ? -1 : ans) << "\n"; return 0; }