#include <bits/stdc++.h>

#define endl '\n'

const int MAXN = 11;
const int MAXK = (1 << 15);
const int INF = 100;

std::vector < std::pair < int, std::bitset < 15 > > > adj[MAXN];

int n, m, k;
std::bitset < 15 > g[MAXN];
int d[MAXN];
std::unordered_set < int > used[MAXN];

std::vector < std::bitset < 15 > > allm[MAXN];

int cost(std::bitset < 15 > v)
{
    return v.count();
}

struct state
{
    int u;
    std::bitset < 15 > masks;
    int c;

    state(){};

    state(int _u, std::bitset < 15 > _masks)
    {
        u = _u;
        masks = _masks;
        c = cost(masks);
    }

    friend bool operator<(state st1, state st2)
    {
        return st1.c > st2.c;
    }
};

void read()
{
    std::cin >> n >> m >> k;
    for(int i = 0; i < n; i++)
    {
        std::cin >> g[i];
    }
    std::bitset < 15 > vc;

    for(int i = 0; i < m; i++)
    {
        int u, v;
        std::cin >> u >> v;

        u--;
        v--;

        std::cin >> vc;

        adj[u].push_back({v, vc});
        adj[v].push_back({u, vc});
    }
}

void gen(int &u, int pos, std::bitset < 15 > &v)
{
    if(pos == k)
    {
        allm[u].push_back(v);
        return;
    }

    gen(u, pos + 1, v);

    if(g[u][pos] == 1)
    {
        v.set(pos);
        gen(u, pos + 1, v);
        v.reset(pos);
    }
}

void genall()
{
    for(int i = 0; i < n; i++)
    {
        std::bitset < 15 > vx;
        gen(i, 0, vx);
    }
}

void solve()
{
    for(int i = 0; i < n; i++)
    {
        d[i] = INF;
    }

    std::priority_queue < state > pq;

    for(std::bitset < 15 > &mask : allm[0])
    {
        pq.push(state(0, mask));
    }

    while(!pq.empty())
    {
        state st = pq.top();
        pq.pop();

        int u = st.u;
        std::bitset < 15 > masks = st.masks;
        int curcost = st.c;

        //cout << "Node : " << u << endl;
        //cout << "Masks : " << masks << endl;
        //cout << "Curcost : " << curcost << endl;
        //cout << endl;

        d[u] = std::min(curcost, d[u]);

        if(u == n - 1)
        {
            std::cout << d[u] << endl;
            return;
        }

        int intmask = (int)masks.to_ulong();
        if(used[u].count(intmask))
            continue;

        used[u].insert(intmask);

        for(std::pair < int, std::bitset < 15 > > &e : adj[u])
        {
            //cout << "Edge to : " << v << endl;
            //cout << "Needs : " << need << endl;

            if((masks & e.second) != e.second)
                continue;

            for(std::bitset < 15 > &newmask : allm[e.first])
            {
                std::bitset < 15 > cur = masks | newmask;

                pq.push(state(e.first, cur));
            }
        }
    }

    std::cout << d[n - 1] << endl;
}

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

    std::ios_base :: sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    read();
    genall();
    solve();

    return 0;
}