#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <unordered_set>

using namespace std;

const int MAX_K = 20;

struct State {
    int city;
    int mask;
    int mask_count;
};

int main() {
    ifstream fin("fart.in");
    ofstream fout("fart.out");

    int N, M, K;
    fin >> N >> M >> K;

    vector<int> city_masks(N);
    for (int i = 0; i < N; ++i) {
        string mask_str;
        fin >> mask_str;
        int mask = 0;
        for (int j = 0; j < K; ++j) {
            if (mask_str[j] == '1') {
                mask |= (1 << j);
            }
        }
        city_masks[i] = mask;
    }

    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        string gas_str;
        fin >> a >> b >> gas_str;
        a--; b--;
        int gas_mask = 0;
        for (int j = 0; j < K; ++j) {
            if (gas_str[j] == '1') {
                gas_mask |= (1 << j);
            }
        }
        adj[a].emplace_back(b, gas_mask);
        adj[b].emplace_back(a, gas_mask);
    }

    queue<State> q;
    q.push({0, city_masks[0], __builtin_popcount(city_masks[0])});

    vector<unordered_set<int>> visited(N);
    visited[0].insert(city_masks[0]);

    int min_masks = K + 1;

    while (!q.empty()) {
        State current = q.front();
        q.pop();

        if (current.city == N - 1) {
            min_masks = min(min_masks, current.mask_count);
            continue;
        }

        for (auto& edge : adj[current.city]) {
            int next_city = edge.first;
            int gas_mask = edge.second;

            int required_mask = gas_mask & ~current.mask;
            if (required_mask == 0) {
                int new_mask = current.mask;
                if (visited[next_city].find(new_mask) == visited[next_city].end()) {
                    visited[next_city].insert(new_mask);
                    q.push({next_city, new_mask, current.mask_count});
                }
            } else {
                int new_mask = current.mask | city_masks[current.city];
                int new_mask_count = current.mask_count + __builtin_popcount(city_masks[current.city] & required_mask);
                if (visited[next_city].find(new_mask) == visited[next_city].end()) {
                    visited[next_city].insert(new_mask);
                    q.push({next_city, new_mask, new_mask_count});
                }
            }
        }
    }

    fout << min_masks << endl;

    fin.close();
    fout.close();
    return 0;
}