#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>>a[20];
bool reach[20][(1<<15)+1];
void solve() {
    int n,m,k;cin>>n>>m>>k;
    int mask[n+1];
    for(int i=0;i<n;i++) {
        string ss;cin>>ss;
        int maskk=0;
        for(int j=ss.size()-1;j>=0;j--) {
            maskk*=2;
            maskk+=ss[j]-'0';
        }
        mask[i+1]=maskk;
    }
    for(int i=0;i<m;i++) {
        int x,y;cin>>x>>y;
        string ss;cin>>ss;
        int maskk=0;
        for(int j=ss.size()-1;j>=0;j--) {
            maskk*=2;
            maskk+=ss[j]-'0';
        }
        a[x].push_back({y, maskk});
        a[y].push_back({x, maskk});
    }
    queue<pair<int,int>>q;
    q.push({1, 0});
    reach[1][0]=1;
    while(q.size()>0) {
        int num=q.front().first;
        int ma=q.front().second;
        q.pop();
        for(int i=0;i<k;i++) {
            if( ((1<<i)&mask[num])!=0 && reach[num][ma|(1<<i)]==0 ) {
                reach[num][ma|(1<<i)]=1;
                q.push({num, ma|(1<<i)});
            }
        }
        for(auto p:a[num]) {
            if( (p.second&ma)==p.second && reach[p.first][ma]==0) {
                reach[p.first][ma]=1;
                q.push({p.first, ma});
            }
        }
    }
    int ans=30;
    for(int i=0;i<(1<<k);i++) {
        if(reach[n][i]) {
            ans=min(ans, __builtin_popcount(i));
        }
    }
    cout<<ans<<endl;
}
int main() {
    freopen("fart.in", "r", stdin);
    freopen("fart.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    solve();
    return 0;
}