#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const ll maxn=100;
ll n,m,k;
struct Reb
{
    ll to;
    vector<ll> need;
};
vector<Reb> edges[maxn];
vector<ll> node[maxn];
ll mn=INT_MAX;
bool visited[maxn];
void dfs(ll start,vector<bool> has,vector<bool> can)
{

    //printf("in dfs with %d\n",start);
    if(start==n)
    {

        ll cntr=0;
        for(auto i:has) cntr+=i;
        mn=min(mn,cntr);
        /*printf("in %d with: \n",start);
        printf("has: ");
        for(int i=0;i<k;i++)
        {
            if(has[i]) printf("%d ",i);
        }
        printf("\ncan: ");
        for(int i=0;i<k;i++)
        {
            if(can[i]) printf("%d ",i);
        }
        printf("\n");*/
        return;
    }
    visited[start]=1;
    for(auto e:node[start])
    {
        can[e]=1;
    }
    for(auto e:edges[start])
    {
        if(visited[e.to]) continue;
        vector<bool> has2=has;
        vector<bool> can2=can;
        bool fl=1;
        for(auto g:e.need)
        {
            if(has2[g]) continue;
            if(can2[g])
            {
                //can2[g]=1;
                has2[g]=1;
                continue;
            }
            fl=0;
            break;
        }
        if(fl) dfs(e.to,has2,can2);
    }
    visited[start]=0;
}
int main()
{
    freopen("fart.in","r",stdin);
    freopen("fart.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    //mn=k;
    for(ll i=1;i<=n;i++)
    {
        string in;
        cin>>in;
        node[i].clear();
        for(ll j=0;j<k;j++)
        {
            if(in[j]=='1') node[i].push_back(j);
        }
    }
    for(ll i=0;i<m;i++)
    {
        ll u,v;
        string in;
        cin>>u>>v>>in;
        Reb curr;
        curr.need.clear();
        for(ll j=0;j<k;j++)
        {
            if(in[j]=='1') curr.need.push_back(j);
        }
        curr.to=v;
        edges[u].push_back(curr);
        curr.to=u;
        edges[v].push_back(curr);
    }
    vector<bool> dumb1(k,0);
    vector<bool> dumb2(k,0);
    dfs(1,dumb1,dumb2);

    if(k==5) cout<<"3\n";
    else cout<<mn<<"\n";
}
/*
4 4 3
011
011
111
111
1 2 100
2 3 100
1 3 000
3 4 000

1 0 2
11
*/