#pragma GCC optimize("O3")

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN = 20;
const int INF = 1e9;
class Graph
{
private:
    struct Edge
    {
        int to;
        vector <int> needMasks;
        Edge(){}
        Edge(int to, vector <int> neededMasks)
        {
            this->to = to;
            this->needMasks = neededMasks;
        }
    };

    int N, K;
    vector <Edge> graph[MAXN];
    vector <int> availableMasksPerTown[MAXN];
    bool used[MAXN];
    bool buyedMasks[MAXN];

    int Generate(int pos, bool *allowedMasks)
    {
        if (pos == K)
        {
            int cnt = 0;
            for (int i = 0; i < K; i++)
            {
                cnt += allowedMasks[i];
                //cout << allowedMasks[i];
            }

            //cout << endl;

            return (Check(allowedMasks)?cnt:INF);
        }

        int ans = INF;
        allowedMasks[pos] = true;
        ans = min(ans, Generate(pos+1, allowedMasks));
        allowedMasks[pos] = false;
        ans = min(ans, Generate(pos+1, allowedMasks));

        return ans;
    }
public:
    Graph(){}
    Graph(int N, int K)
        :N(N), K(K){}

    void AddTownInfo(int town, string& input)
    {
        for (int i = 0; i < (int)input.size(); i++)
        {
            if (input[i] == '0')
                continue;

            availableMasksPerTown[town].push_back(i);
        }
    }
    void AddEdge(int u, int v, string& input)
    {
        vector <int> neededMasks;
        for (int i = 0; i < (int)input.size(); i++)
        {
            if (input[i] == '0')
                continue;

            neededMasks.push_back(i);
        }

        graph[u].emplace_back(v, neededMasks);
        graph[v].emplace_back(u, neededMasks);
    }

    bool Check(const bool *allowedMasks)
    {
        memset(used, false, sizeof(used));
        memset(buyedMasks, false, sizeof(buyedMasks));

        queue <int> q;
        q.push(1);
        used[1] = true;

        for (int availableMask: availableMasksPerTown[1])
        {
            if (allowedMasks[availableMask] == true)
            {
                buyedMasks[availableMask] = true;
            }
        }

        while (!q.empty())
        {
            int node = q.front();
            q.pop();


            for (const Edge& edge: graph[node])
            {
                if (used[edge.to])
                    continue;

                bool canEnter = true;
                for (int neededMask:edge.needMasks)
                {
                    if (buyedMasks[neededMask] == false)
                    {
                        canEnter = false;
                        break;
                    }
                }

                if (canEnter == false)
                    continue;

                for (int availableMask: availableMasksPerTown[edge.to])
                {
                    if (allowedMasks[availableMask] == true)
                    {
                        buyedMasks[availableMask] = true;
                    }
                }
                used[edge.to] = true;
                q.push(edge.to);
            }
        }

        return used[N];
    }


    int Solve()
    {
        bool allowedMasks[MAXN];
        memset(allowedMasks, false, sizeof(allowedMasks));

        return this->Generate(0, allowedMasks);
    }
};
int main()
{
    #ifndef __LOCAL__
        freopen("fart.in", "r", stdin);
        freopen("fart.out", "w", stdout);
    #endif // __LOCAL__

    int N, M, K;
    cin >> N >> M >> K;

    Graph *graph = new Graph(N, K);

    for (int i = 1; i <= N; i++)
    {
        string s;
        cin >> s;
        graph->AddTownInfo(i, s);
    }

    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;
        string s;
        cin >> s;

        graph->AddEdge(u, v, s);
    }

    cout << graph->Solve() << endl;
    delete graph;

    return 0;
}