#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 20, MAXMASK = 1e5+10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, m, k;
long long sell[MAXN][MAXN];
vector < pair < long long, long long > > g[MAXN];
void read()
{
    cin >> n >> m >> k;
    for (long long i = 1; i <= n; ++ i)
    {
        string s;
        cin >> s;
        for (long long j = 0; j < s.size(); ++ j)
        {
            if(s[j] == '1')sell[i][j] = 1;
        }
    }
    for (long long i = 1; i <= m; ++ i)
    {
        long long u, v;
        cin >> u >> v;

        string s;
        cin >> s;
        long long mask = 0;
        for (long long j = 0; j < s.size(); ++ j)
        {
            if(s[j] == '1')mask = (mask | (1 << j));
        }
        g[u].push_back(make_pair(v, mask));
        g[v].push_back(make_pair(u, mask));
    }
}

long long ans = 0;
long long buyit = 0, didit = 0;
long long visited[MAXN][MAXN];
void rec(long long i, long long mask, int cnt)
{

    //cout << i << " " << mask << " " << dp[i][mask] << endl;
    if(i < 1 || i > n)return;
    visited[i][cnt] = 1;
    int new_ones = 0;
    for (long long j = 0; j < k; ++ j)
        {

            if(!(mask & (1 << j)) && ((1 << j) & buyit) && sell[i][j])
            {

                mask = (mask | (1 << j));
                new_ones ++;
            }

        }
    for (auto &[to, need]: g[i])
    {
        if(visited[to][cnt + new_ones])continue;
        if(need != (need & mask))continue;
        rec(to, mask, cnt + new_ones);
    }
    if(n == i)
    {
        didit = 1;
    }
}
int main()
{
    speed();

    freopen("fart.in", "r", stdin);
    freopen("fart.out", "w", stdout);


    read();
    ans = k+1;

    for (long long mask = 0; mask < (1 << (k)); ++ mask)
    {
        long long costt = 0;
        buyit = 0;
        didit = 0;
        for (long long j = 0; j < k; ++ j)
        {
            if((1 << j) & mask)
            {
                costt ++;
                buyit = (buyit | (1 << j));
            }
        }
        memset(visited, 0, sizeof(visited));

        rec(1, 0, 0);
        if(didit)ans = min(ans, costt);
    }
    assert(ans != k+1);
    cout << ans << endl;
    return 0;
}