// we both did the best we could do, underneath the same moon, in different galaxies

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
//#define int long long
typedef long long ll;
typedef long double ld;
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ifstream cin("fart.in");
    ofstream cout("fart.out");
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> sold(n, 0);
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < k; j++) if (s[j] == '1') sold[i] |= (1 << j);
    }
    vector<vector<pair<int, int> > > g(n);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        x--, y--;
        string s;
        cin >> s;
        int c = 0;
        for (int j = 0; j < k; j++) if (s[j] == '1') c |= (1 << j);
        g[x].push_back({ y, c });
        g[y].push_back({ x, c });
    }
    vector<vector<int> > d(n, vector<int>((1 << k), -1));
    queue<pair<int, int> > q;
    q.push({ 0, 0 });
    int ans = k + 1;
    while (!q.empty())
    {
        int u = q.front().first;
        int x = q.front().second;
        q.pop();
        if (u == n - 1)
        {
            int cnt = 0;
            for (int i = 0; i < k; i++) if (x & (1 << i)) cnt++;
            ans = min(ans, cnt);
        }
        int can = (sold[u] ^ x) & sold[u];
        for (int ex = can; ex; ex = ((ex - 1) & can))
        {
            int nwx = x | ex;
            if (d[u][nwx] == -1)
            {
                d[u][nwx] = d[u][x] + 1;
                q.push({ u, nwx });
            }
        }
        for (pair<int, int> p : g[u]) if ((x & p.second) == p.second && d[p.first][x] == -1)
        {
            d[p.first][x] = d[u][x] + 1;
            q.push({ p.first, x });
        }
    }
    cout << (ans == k + 1 ? -1 : ans) << "\n";
    return 0;
}