dianaMakeSpanLinearAccClean

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <fstream>

#define MAXN 100000// maximum number of nodes in graph
#define NMAX 100 + 5
#define TMAX 1000 + 5
using namespace std;


int n, m, k;
int start, destination, weight;
int startOfNewAgent;
int vertex, steps, timeStamp;


std::vector<int> agents;
std::vector<std::vector<std::pair<int, int>>> targetPath;

// edges in the original graph
int edges[NMAX][NMAX];

int viz[NMAX][TMAX];


struct Edge
{
    Edge(int _a, int _b, int _c, int _f, int _w) {
        a = _a; b = _b; c = _c; f = _f; w = _w;
    }
    ~Edge() { };
    int a; //from
    int b; //to
    int c; //capacity
    int f; //flow
    int w; //weight
    Edge* r;
};


const int MAX_DIST = 2000000; //do not choose INT_MAX because you are adding weights to it
std::vector<Edge*> adj[MAXN];
int distances[MAXN];
Edge* parents[MAXN];

int nodecount = 1000;
int source;
int sink;

std::vector<std::vector<int>> layer_on_timestamp;
std::vector<std::vector<int>> layer_on_double_timestamp;
std::vector<int> sinks;

std::vector<int> possibleMakeSpan;

// bellman - ford
bool find_path(int from, int to, std::vector<Edge*>& output)
{
    std::fill(distances, distances+nodecount, MAX_DIST);
    std::fill(parents, parents+nodecount, (Edge*)0);
    distances[from] = 0;

    bool updated = true;
    while(updated)
    {
        updated = false;
        for(int j = 0; j < nodecount; ++j)
            for(int k = 0; k < (int)adj[j].size(); ++k){
                Edge* e = adj[j][k];
                if( e->f >= e->c ) continue;
                if( distances[e->b] > distances[e->a] + e->w )
                {
                    //std::cerr << distances[e->b] << " " << distances[e->a] << " " << e->w << std::endl;
                    distances[e->b] = distances[e->a] + e->w;
                    parents[e->b] = e;
                    updated = true;
                }
            }
    }
    output.clear();
    if(distances[to] == MAX_DIST) return false;
    int cur = to;
    while(parents[cur])
    {
        output.push_back(parents[cur]);
        cur = parents[cur]->a;
    }
    return true;
}


// MAX FLOW MIN COST IMPLEMENTATION
int min_cost_max_flow(int source, int sink)
{
    int total_cost = 0;

    int totalFlow = 0;
    std::vector<Edge*> p;
    while(find_path(source, sink, p))
    {
        int flow = INT_MAX;
        for(int i = 0; i < p.size(); ++i)
            if(p[i]->c - p[i]->f < flow) flow = p[i]->c - p[i]->f;

        int cost = 0;
        for(int i = 0; i < p.size(); ++i) {
            cost += p[i]->w;
            p[i]->f += flow;
            p[i]->r->f -= flow;
        }
        cost *= flow; //cost per flow
        total_cost += cost;
        totalFlow += flow;
    }

    return totalFlow;
}

int run(int source, int sink) {
    const auto max_flow = min_cost_max_flow(source, sink);
    for (int i = 0; i < nodecount; ++i) {

        for (unsigned int j = 0; j < adj[i].size(); ++j)
            delete adj[i][j];
        adj[i].clear();
    }

    return max_flow;
}


void add_edge(int a, int b, int c, int w)
{
    Edge* e = new Edge(a, b, c, 0, w);
    Edge* re = new Edge(b, a, 0, 0, -w);
    e->r = re;
    re->r = e;
    adj[a].push_back(e);
    adj[b].push_back(re);
}


void reset() {
    sinks.clear();
    for (int i = 0; i < NMAX; ++i)
        for (int j = 0; j < NMAX; ++j)
            viz[i][j] = false;

    layer_on_timestamp.clear();
    layer_on_double_timestamp.clear();

}
void constructGraph(int max_timestamp) {


    // construct graph
    source = 0;
    sink = 1;

    int id = 2;

    reset();

    layer_on_timestamp.resize(TMAX + 1, vector<int>(NMAX + 1, -1));
    layer_on_double_timestamp.resize(TMAX + 1, vector<int>(NMAX + 1, -1));
    sinks.resize(k + 1);

    // create the sink and the corresponding edges
    for(int target = 0; target < k; target ++) {
        sinks[target] = id ++;
        // add edges to the sink from the target
        add_edge(sinks[target], sink, 1, 0);
    }

    // construct rest of the matrix
    std::queue<std::pair<int, int>> queue; // node, timestamp pair

    // go through all the agents and create edges from the source
    for(int i = 0; i < k ; i++) {
        queue.push(std::make_pair(agents[i], 0));
        layer_on_timestamp[0][agents[i]] = id ++;
        add_edge(source, layer_on_timestamp[0][agents[i]], 1, 0);
    }

    while(!queue.empty()) {
        std::pair<int, int> current = queue.front();
        queue.pop();

        int node = current.first;
        int timestamp = current.second;

        if (timestamp > max_timestamp || viz[node][timestamp])
            continue;

        viz[node][timestamp] = 1;

        if (layer_on_double_timestamp[timestamp][node] == -1)
            layer_on_double_timestamp[timestamp][node] = id ++;


        // stay in place
        if(timestamp + 1 <= max_timestamp) {
            if(layer_on_timestamp[timestamp + 1][node] == -1)
                layer_on_timestamp[timestamp + 1][node] = id ++;

            add_edge(layer_on_double_timestamp[timestamp][node], layer_on_timestamp[timestamp + 1][node], 1,
                     1);
            queue.push(std::make_pair(node, timestamp + 1));
        }

        for (int i = 0; i < n; i++) {
            int forward = edges[node][i];

            if (timestamp + forward <= max_timestamp && forward != 0) {
                if (layer_on_timestamp[timestamp + forward][i] == -1)
                    layer_on_timestamp[timestamp + forward][i] = id ++;

                add_edge(layer_on_double_timestamp[timestamp][node], layer_on_timestamp[timestamp + forward][i], 1,
                         forward);
                queue.push(std::make_pair(i, timestamp + forward));
            }
        }

    }

    // create edges from targets to the sink target
    for(int target = 0; target < k; target ++) {
        int sink_of_target = sinks[target];

        std::vector<std::pair<int, int>> path = targetPath[target];

        // position -> vertex, timestamp
        for (auto position: path) {
            if (layer_on_double_timestamp[position.second][position.first] == -1)
                layer_on_double_timestamp[position.second][position.first] = id ++;

            add_edge(layer_on_double_timestamp[position.second][position.first], sink_of_target, 1, 0);
        }

        std::pair<int, int> last_node = path.back();
        for(int i = last_node.second + 1; i <= max_timestamp; i++) {
            if (layer_on_double_timestamp[i][last_node.first] == -1)
                layer_on_double_timestamp[i][last_node.first] = id ++;

            add_edge(layer_on_double_timestamp[i][last_node.first], sink_of_target, 1, 0);
        }
    }

    for (int t = 0; t <= max_timestamp; ++t)
        for (int i = 0; i < n; ++i)
            if (layer_on_timestamp[t][i] != -1 && layer_on_double_timestamp[t][i] != -1) {
                add_edge(layer_on_timestamp[t][i], layer_on_double_timestamp[t][i], 1, 0);
            }


    nodecount = id + 5;
}

int main() {
    //std::ifstream cin("date.in");
//    freopen("date.in" , "r", stdin);

    // read vertex num, edges num and k (agent/target count)
    std::cin >> n >> m >> k;

    // read graph
    for(int i = 0; i < m; i++) {
        std::cin >> start >> destination >> weight;

        // directed graph add just one time
        edges[start][destination] = weight;
    }

    // see where the agents are starting -> value of index for each
    for(int i = 0; i < k; i++) {
        std::cin >> startOfNewAgent;
        agents.push_back(startOfNewAgent);
    }

    // see the steps that each target makes -> (vertex, time)
    for(int i = 0; i < k; i++) {
        std::cin >> steps;

        std::vector<std::pair<int, int>> path;
        for (int j = 0; j < steps; j++) {
            std::cin >> vertex >> timeStamp;
            path.push_back(std::make_pair(vertex, timeStamp));

        }

        targetPath.push_back(path);
    }

    int maxTime = -1;

    for (int t = 1; t <= TMAX; ++t) {
        constructGraph(t);
        int ans = run(0, 1);
        if (ans == k) // cuplaj
        {
            maxTime = t;
            break;
        }
    }

    cout << maxTime << '\n';
    return 0;
}