/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("avx2")
#pragma GCC optimize("unroll-loops")*/

#define ll int

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

const ll MAXN=1e1+5,INF=LLONG_MAX;
ll n,m,K,a[11],k2,d[11][32769],cnt[32769];
vector<pair<ll,ll> > v[11];
bool f[11][32769];

ll convert(string s){
    ll ans=0,k=1;

    for(ll i=0;i<s.size();++i){
        ans+=k*(s[s.size()-1-i]-'0');
        k*=2;
    }

    return ans;
}

ll calccnt(ll k){
    ll ans=0;
    while(k>0){
        ans+=k%2;
        k/=2;
    }
    return ans;
}

void solve(){
    cin>>n>>m>>K;
    string in;
    for(ll i=1;i<=n;++i){
        cin>>in;
        a[i]=convert(in);
    }

    ll p,q;
    for(ll i=0;i<m;++i){
        cin>>p>>q>>in;
        v[p].push_back({q,convert(in)});
        v[q].push_back({p,convert(in)});
    }

    k2=1;
    for(ll i=0;i<K;++i) k2*=2;
    for(ll i=0;i<k2;++i) cnt[i]=calccnt(i);

    for(ll i=1;i<=n;++i) for(ll j=0;j<k2;j++) d[i][j]=INT_MAX;
    set<pair<ll,pair<ll,ll> > > s;
    s.insert({0,{-1,0}});
    ll k,td,tm,nd,ans;
    while(!s.empty()){
        k=-s.begin()->second.first;
        td=s.begin()->first;
        tm=s.begin()->second.second;
        if(k==n){ans=td; break;}
        s.erase(s.begin());
        if(f[k][tm]==1) continue;
        f[k][tm]=1;
        d[k][tm]=td;

        for(auto ch : v[k]){
            for(ll i=0;i<k2;++i){
                if(f[ch.first][i]==1) continue;
                nd=cnt[i];
                if(nd>=d[ch.first][i]) continue;
                if((i&ch.second)>=ch.second && (i&tm)>=tm && ((tm|a[k])&i)>=i){
                    d[ch.first][i]=nd;
                    s.insert({nd,{-ch.first,i}});
                }
            }
        }
    }

    cout<<ans;
}

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

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    ll t=1;
    //cin>>t;
    while(t--) solve();

    return 0;
}