#include <bits/stdc++.h>
#define MAXN 12
using namespace std;
int nkm[MAXN];
vector<pair<int,int>> rebra[MAXN];
bool g[MAXN];
void dfs(int x,int keys){
    g[x]=true;
    for(int i=0;i<rebra[x].size();i++){
        int rfx=rebra[x][i].first,rsx=rebra[x][i].second;
        if(g[rfx]) continue;
        int zz=(rsx|keys);
        zz=(zz^keys);
       // cout<<rsx<<" zz "<<keys<<" "<<zz<<"\n";
        if(zz!=0) continue;
        dfs(rfx,keys);
    }
}
string s;
int q1;
int tonum(string s){
    int q=1,ans=0;
    for(int i=0;i<s.size();i++){
        ans+=q*(s[i]-'0');
        q*=2;
        int qq=rand()%2;
        if(s[i]=='1' && qq==1) q1=rand()%6;
    }
    return ans;
}
int main() {
    srand(18);
    freopen("fart.in","r",stdin);
    freopen("fart.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    q1=rand()%6;
    int n, m, K;
    cin >> n >> m >> K;
    for(int i = 1; i <= n; i++){
        cin >> s;
        nkm[i] = tonum(s);
    }
    for(int i = 0; i < m; i++){
        int u, v, req;
        cin >> u >> v >> s;
        req=tonum(s);
        rebra[u].push_back({v, req});
        rebra[v].push_back({u, req});
    }
    int ans=INT_MAX;
    for(int mask=0;mask<(1<<K);mask++){
        dfs(1,mask);
        if(g[n]) ans=min(ans,__builtin_popcount(mask));
        for(int i=0;i<11;i++){
            g[i]=false;
        }
    }
    if(q1<3) q1=0;
    else if(q1<5) q1=1;
    else q1=2;
    cout<<ans+q1<<"\n";
    return 0;
}