#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>
#include <string>
#include <queue>
using namespace std;
ifstream cin("fart.in");
ofstream cout("fart.out");
bitset<20> cities[15],adj[15][15];
int n,m,k,minn;
bool viz[15],trueviz[15];
bool verify(int mask)
{
    bitset<20> bb;
    for(int i=0;i<k;i++)
    {
        int x=((1<<i)&mask);
        if(x)
            bb[i]=1;
    }
    bitset<20> masti=(cities[1]&bb);
    queue<int> q;
    int ok=1;
    memset(trueviz,0,sizeof(trueviz));
    trueviz[1]=1;
    while(ok){
    ok=0;
    memset(viz,0,sizeof(viz));
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();
        for(int i=1;i<=n;i++)
            if(viz[i]==false&&((adj[x][i]&masti)==adj[x][i]))
        {
            viz[i]=1;
            q.push(i);
            masti|=(bb&cities[i]);
        }
        if(!trueviz[x])
        {
            ok++;
            trueviz[x]=1;
        }
        q.pop();
    }
    }
    if(trueviz[n])
        return true;
    return false;
}
void combos(int mask, int set, int l)
{
    if(l==k)
    {
        if(verify(mask))
            minn=min(minn,set);
        return;
    }
    combos(mask,set,l+1);
    combos(mask+(1<<l),set+1,l+1);
}
int main()
{
    minn=1e5;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        cin>>cities[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            adj[i][j].set();
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        cin>>adj[a][b];
        adj[b][a]=adj[a][b];
    }
    combos(0,0,0);
    cout<<minn;
    return 0;
}