#include <bits/stdc++.h>
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<int> 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<vector<pair<int, int>>> 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<vector<int>> dp(N + 1, vector<int>(MAX_MASK, INF));

    // Priority queue with (cost, city, mask) - using Dijkstra's approach
    typedef tuple<int, int, int> State;
    priority_queue<State, vector<State>, greater<State>> 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;
}