#include <bits/stdc++.h>
# define clr(x,a)        memset(x,a,sizeof(x))
# define all(a)          a.begin(), a.end()
# define deb(x)          cout<<#x<<"=="<<x<<endl;
# define deb2(x, y)      cout<<"("<<#x<<", "<<#y<<")==("<<x<<", "<<y<<")\n";
# define pb              push_back
# define sc              scanf
# define pr              printf
# define nd              second
# define tc              int t; cin>>t; while(t--)
# define rev(s)          reverse(s.begin(),s.end())
# define linija          cout<<"___________\n";
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int mxN=200005, mxM=5005, LOG=25, inf = 2e9;
const long long mod=1e9+7;
template<typename T> T nzd(T a, T b){if(b==0) return a;else return nzd(b, a%b);}
template<typename T> T nzs(T a, T b){return(a*(b/nzd(a,b)));}
template<typename T> T stepenuj(T e, T n){T x=1,p=e;while(n){if(n&1)x=(x*p)%mod;p=(p*p)%mod;n>>=1;}return x;}
template<typename T> inline T na2(T x){return x*x;}

int n, m, k, res = 1110, u, v;
string maske[25];
vector<pair<int, string>> graf[20];
pair<int, string> pom;
int visited[25], glob;
string potreba, imam;

void make_potreba(int x){
   potreba.clear();
   imam.clear();

   while(x > 0){
      if(x&1) potreba.pb('1');
      else potreba.pb('0');
      x /= 2;
   }
   while(potreba.size() < k) potreba.pb('0');

   for(int i = 0; i < k; i++) imam.pb('0');
}

inline bool compare(string& p){
   //cout << "comp: " << p << endl;
   for(int i = 0; i < k; i++){
      if(imam[i] == '0' && p[i] == '1') return 0;
   }
   return 1;
}

void kupi(string tren){
   for(int i = 0; i < k; i++){
      if(tren[i] == '1' && potreba[i] == '1') imam[i] = 1;
   }
}
void dfs(int node){
   visited[node] = glob;
   kupi(maske[node]);
   for(int i = 0; i < graf[node].size(); i++){
      pom = graf[node][i];
      //deb(pom.first);
      if(visited[pom.first] != glob && compare(pom.second)){
         dfs(pom.first);
      }
      //cout << "i:  " << i << endl;
   }
}

void check_res(){
   //cout << "checkres\n";
   int tren = 0;
   for(int i = 0; i < k; i++){
      if(potreba[i] == '1') tren++;
   }
   res = min(res, tren);
}

void solve(){
   int kraj = (1<<k);
   for(int i = 0; i < kraj; i++){
      make_potreba(i);
      glob++;
      dfs(1);
      if(visited[n] == glob) check_res();
   }
}

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

   cin >> n >> m >> k;
   for(int i = 1; i <= n; i++){
      cin >> maske[i];
   }

   for(int i = 1; i <= m; i++){
      cin >> u >> v >> pom.second;
      pom.first = v;

      graf[u].pb(pom);

      pom.first = u;
      graf[v].pb(pom);
   }

   //cout << "solvujem\n";
   solve();

   //cout << res << endl;
   freopen("fart.out", "w", stdout);
   cout << res << endl;



   return 0;
}