#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <limits>
using namespace std;

int main(){
    freopen( "fart.in", "r", stdin );
    freopen( "fart.out", "w", stdout );
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    // Прочитаме кои маски се продават във всеки град (като битова маска)
    vector<int> cityMasks(N, 0);
    for (int i = 0; i < N; i++){
        string s;
        cin >> s;
        int mask = 0;
        for (int j = 0; j < K; j++){
            if (s[j] == '1'){
                mask |= (1 << j);
            }
        }
        cityMasks[i] = mask;
    }

    // Построяване на графа – всеки път има газова битова маска
    vector<vector<pair<int,int>>> graph(N);
    for (int i = 0; i < M; i++){
        int a, b;
        string gas;
        cin >> a >> b >> gas;
        a--; b--;
        int gasMask = 0;
        for (int j = 0; j < K; j++){
            if (gas[j] == '1'){
                gasMask |= (1 << j);
            }
        }
        graph[a].push_back({b, gasMask});
        graph[b].push_back({a, gasMask});
    }

    // Ще използваме 0-1 BFS върху състояния: (град, maskState)
    // Разстоянието ще е броят на закупените маски
    const int INF = numeric_limits<int>::max();
    vector<vector<int>> dist(N, vector<int>(1 << K, INF));

    // Начално състояние: град 0 (т.е. 1 според условието), без закупени маски.
    deque<pair<int,int>> dq;
    dist[0][0] = 0;
    dq.push_back({0, 0});

    while(!dq.empty()){
        auto [u, mset] = dq.front();
        dq.pop_front();
        int cost = dist[u][mset];

        // Ако сме достигнали град N, извеждаме минималната цена.
        if(u == N - 1){
            cout << cost << "\n";
            return 0;
        }

        // 1. Покупка на маска (ако градът продава дадена и я нямаме)
        int available = cityMasks[u];
        for (int i = 0; i < K; i++){
            // Ако градът продава маска за газ i и я нямаме още
            if ((available & (1 << i)) && ((mset & (1 << i)) == 0)){
                int newMaskState = mset | (1 << i);
                if (dist[u][newMaskState] > cost + 1){
                    dist[u][newMaskState] = cost + 1;
                    dq.push_back({u, newMaskState}); // покачване на цената с 1
                }
            }
        }

        // 2. Преминаване по път (ако с наличните маски покриваме изискванията за газове)
        for (auto &edge : graph[u]){
            int v = edge.first;
            int req = edge.second;
            // Ако разполагаме с всички необходими маски за този път
            if ((mset & req) == req){
                if (dist[v][mset] > cost){
                    dist[v][mset] = cost;
                    dq.push_front({v, mset}); // преминаване без допълнителна цена
                }
            }
        }
    }

    // Ако не можем да достигнем град N, извеждаме -1 (но според условието винаги има път)
    cout << -1 << "\n";
    return 0;
}