#include #define endl '\n' using namespace std; const long long MAXN = 20, MAXMASK = 1e5+10; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } long long n, m, k; long long sell[MAXN][MAXN]; vector < pair < long long, long long > > g[MAXN]; void read() { cin >> n >> m >> k; for (long long i = 1; i <= n; ++ i) { string s; cin >> s; for (long long j = 0; j < s.size(); ++ j) { if(s[j] == '1')sell[i][j] = 1; } } for (long long i = 1; i <= m; ++ i) { long long u, v; cin >> u >> v; string s; cin >> s; long long mask = 0; for (long long j = 0; j < s.size(); ++ j) { if(s[j] == '1')mask = (mask | (1 << j)); } g[u].push_back(make_pair(v, mask)); g[v].push_back(make_pair(u, mask)); } } long long ans = 0; long long buyit = 0, didit = 0; long long visited[MAXN][MAXN]; void rec(long long i, long long mask, int cnt) { //cout << i << " " << mask << " " << dp[i][mask] << endl; if(i < 1 || i > n)return; visited[i][cnt] = 1; int new_ones = 0; for (long long j = 0; j < k; ++ j) { if(!(mask & (1 << j)) && ((1 << j) & buyit) && sell[i][j]) { mask = (mask | (1 << j)); new_ones ++; } } for (auto &[to, need]: g[i]) { if(visited[to][cnt + new_ones])continue; if(need != (need & mask))continue; rec(to, mask, cnt + new_ones); } if(n == i) { didit = 1; } } int main() { speed(); freopen("fart.in", "r", stdin); freopen("fart.out", "w", stdout); read(); ans = k+1; for (long long mask = 0; mask < (1 << (k)); ++ mask) { long long costt = 0; buyit = 0; didit = 0; for (long long j = 0; j < k; ++ j) { if((1 << j) & mask) { costt ++; buyit = (buyit | (1 << j)); } } memset(visited, 0, sizeof(visited)); rec(1, 0, 0); if(didit)ans = min(ans, costt); } assert(ans != k+1); cout << ans << endl; return 0; }