#include <iostream> 
#include <fstream> 
#include <vector> 
#include <string> 
#include <deque> 
#include <unordered_map> 
#include <algorithm> 
using namespace std;

struct State {
    int city; 
    string mask; // Низ с дължина k: '1' показва, че маската за съответния газ е закупена. 
    int cost; // Брой закупени маски до момента. 
};

int main() {
    ifstream inp("fart.in");
    int n, m, k;
    inp >> n >> m >> k;

    // Четем кои маски се продават във всеки град.
    // За град i запазваме низ от дължина k – ако на позиция j има '1', в града се продава маска за газ j+1.
    vector<string> citySales(n + 1);
    for (int i = 1; i <= n; i++) {
        inp >> citySales[i];
    }

    // Четем графа – всеки път свързва два града и има низ, указващ кои газове отделя.
    vector<vector<pair<int, string>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        string hazard;
        inp >> a >> b >> hazard;
        adj[a].push_back({ b, hazard });
        adj[b].push_back({ a, hazard });
    }
    inp.close();

    // dp[град] – за всеки град съхраняваме минималния брой закупени маски за даден набор (представен като низ).
    vector<unordered_map<string, int>> dp(n + 1);
    const int INF = 1e9;
    string init(k, '0');
    dp[1][init] = 0;

    deque<State> dq;
    dq.push_back({ 1, init, 0 });

    while (!dq.empty()) {
        State cur = dq.front();
        dq.pop_front();
        int city = cur.city;
        string mask = cur.mask;
        int cost = cur.cost;

        // Ако текущата цена не съвпада с най-доброто намерено за това състояние – прескачаме.
        if (dp[city][mask] != cost)
            continue;

        // Опция 1: Закупуваме маски, които се продават в текущия град и все още не са закупени.
        for (int j = 0; j < k; j++) {
            if (citySales[city][j] == '1' && mask[j] == '0') {
                string newMask = mask;
                newMask[j] = '1';
                int newCost = cost + 1;
                if (!dp[city].count(newMask) || dp[city][newMask] > newCost) {
                    dp[city][newMask] = newCost;
                    dq.push_back({ city, newMask, newCost });
                }
            }
        }

        // Опция 2: Преминаваме към съседен град, ако текущият набор от закупени маски покрива
        // газовете, отделяни по пътя.
        for (auto& edge : adj[city]) {
            int nextCity = edge.first;
            string hazard = edge.second;
            bool canPass = true;
            for (int j = 0; j < k; j++) {
                if (hazard[j] == '1' && mask[j] == '0') {
                    canPass = false;
                    break;
                }
            }
            if (canPass) {
                int newCost = cost;
                if (!dp[nextCity].count(mask) || dp[nextCity][mask] > newCost) {
                    dp[nextCity][mask] = newCost;
                    dq.push_front({ nextCity, mask, newCost });
                }
            }
        }
    }

    // Намираме минималната цена за град N, разглеждайки всички състояния.
    int ans = INF;
    for (auto& entry : dp[n]) {
        ans = min(ans, entry.second);
    }

    ofstream out("fart.out");
    out << ans << endl;
    out.close();
    return 0;
}