#include<bits/stdc++.h>
using namespace std;

long long n, m, p;
string path[13][13];
bool is[13][13];
string s[16];

bool iz[13][35000];

bool alowed(string a, string b)
{
    for (long long i=0; i<a.size(); i++)
    {
        if (b[i]=='1' && a[i]=='0') return false;
    }
    return true;
}

string merg(string a, string b)
{
    string ans;
    for (long long i=0; i<a.size(); i++)
    {
        if (a[i]=='1' || b[i]=='1')
        {
            ans.push_back('1');
        }
        else
        {
            ans.push_back('0');
        }
    }

    return ans;
}

long long BS(string g)
{
    long long ans=0;

    for (long long i=g.size(); i>=0; i--)
    {
        ans=ans+(g[i]-'0')*(1<<(g.size()-i-1));
    }
    return ans;
}

long long answer=1'000'000'000'000;

void dfs(long long x, string w, string maski)
{
    //cout<<x<<" "<<w<<" "<<maski<<endl;
    if (x==n)
    {
        //cout<<maski<<endl;
        long long br=0;
        for (long long i=0; i<maski.size(); i++)
        {
            br=br+(maski[i]-'0');
        }

        answer=min(answer, br);
        return;
    }

    if (iz[x][BS(maski)]) return;

    iz[x][BS(maski)]=true;
    for (long long i=1; i<=n; i++)
    {
        if (!is[x][i]) continue;

        long long next=i;

        if (alowed(w, path[x][next]))
        {
            dfs(next, merg(w, s[next]), merg(maski, path[x][next]));
        }
    }
    return;
}

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


    cin>>n>>m>>p;

    if (n==1)
    {
        cout<<0<<endl;
        return 0;
    }

    for (long long i=1; i<=n; i++)
    {
        cin>>s[i];
    }

    for (long long i=0; i<m; i++)
    {
        long long x, y;
        cin>>x>>y;
        string s1;
        cin>>s1;
        is[x][y]=true;
        is[y][x]=true;
        path[x][y]=s1;
        path[y][x]=s1;
    }

    string g;
    for (long long i=1; i<=p; i++) g.push_back('0');

    dfs(1, s[1], g);
    cout<<answer<<endl;
    return 0;
}