#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second

using namespace std;

void fileIO()
{
    freopen("fart.in", "r", stdin);
    freopen("fart.out", "w", stdout);
}
void fastIO()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int MAXN=105;
const int MAXK=20;

int n,m,k;
int a[MAXN];
vector<pair<int,int> > adj[MAXN];
bool used[MAXN];
bool vis[MAXN];
bool fl=0;
int cur=0;

void dfs(int v,int mask)
{
    used[v]=1;
    if(v==n)
    {
        fl=1;
        return;
    }
    vis[v]=1;
    cur|=(a[v]&mask);
    for(int i=0;i<adj[v].size();i++)
    {
        auto [u,w]=adj[v][i];
        if(vis[u]) continue;
        if((cur|w)==cur) 
        {
            dfs(u,mask);
            if(fl) return;
            i=0;
        }
    }
    //vis[v]=0;
}

int main()
{
    fastIO();
    fileIO();

    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        a[i]=0;
        for(int j=0;j<k;j++)
        {
            if(s[j]=='1') a[i]|=(1<<j);
        }
    }
    for(int i=0;i<m;i++)
    {
        int u,v;
        string s;
        cin>>u>>v>>s;
        int cur=0;
        for(int j=0;j<k;j++)
        {
            if(s[j]=='1') cur|=(1<<j);
        }
        adj[u].push_back({v,cur});
        adj[v].push_back({u,cur});
    }

    int ans=k;
    for(int mask=0;mask<(1<<k);mask++)
    {
        int cnt=0;
        for(int j=0;j<k;j++)
        {
            if(mask&(1<<j)) cnt++;
        }
        if(cnt>=ans) continue;
        //cout<<mask<<endl;
        for(int i=1;i<=n;i++) 
        {
            used[i]=0;
            vis[i]=0;
        }
        fl=0;
        cur=0;
        dfs(1,mask);
        if(used[n]==1) ans=min(ans,cnt); // cout<<mask<<endl;
    }
    
    cout<<ans<<endl;

    return 0;
}