makeSpanNoCollision

#include <bits/stdc++.h>

using namespace std;

#define TMAX (int)(1000)
#define NMAX (int)(100)
#define INF (int)(1e9)
#define smallINF (int)(1e6) // avoid overflow: 25 * 25 * 1e6 <= INT_MAX
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)
#define fo(i, n) for(int i=0,_n=(n);i<_n;i++)

void __print(int x) { cerr << x; }

void __print(long x) { cerr << x; }

void __print(long long x) { cerr << x; }

void __print(unsigned x) { cerr << x; }

void __print(unsigned long x) { cerr << x; }

void __print(unsigned long long x) { cerr << x; }

void __print(float x) { cerr << x; }

void __print(double x) { cerr << x; }

void __print(long double x) { cerr << x; }

void __print(char x) { cerr << '\'' << x << '\''; }

void __print(const char *x) { cerr << '\"' << x << '\"'; }

void __print(const string &x) { cerr << '\"' << x << '\"'; }

void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V, typename W>
void __print(const std::tuple<T, V, W> &x) {
    cerr << '{';
    __print(std::get<0>(x));
    cerr << ',';
    __print(std::get<1>(x));
    cerr << ',';
    __print(std::get<2>(x));
    cerr << '}';
}

template<typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}

template<typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}

void _print() { cerr << "]\n"; }

template<typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}

#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif




int N, M, K, x, y, w, t;
int source, sink;
vector<vector<pair<int, int>>> G; // Directed graph, {neigh, time}
vector<int> starts; // stores the starting node of each Agent
vector<vector<pair<int, int>>> paths; // stores path of each Target

class Edge {
public:
    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;

};

class MaxFlowMinCost {
public:

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

    MaxFlowMinCost(int _nodes) {
        this->adj.resize(this->MAX_NODES);
        this->node_count = _nodes;
    }


    bool find_path(int from, int to, vector<Edge *> &output) // Assume no negative paths
    {
        fill(distances, distances + node_count, MAX_DIST);
        fill(parents, parents + node_count, (Edge *) 0);
        distances[from] = 0;

        bool updated = true;
        while (updated) {
            updated = false;
            for (int j = 0; j < node_count; ++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) {
                        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;
    }

    pair<int, int> min_cost_max_flow(int source, int sink) {
        int total_cost = 0;
        int total_flow = 0;
        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;
            }
            total_flow += flow;
            cost *= flow; //cost per flow
            total_cost += cost;
        }
        return {total_flow, total_cost};
    }

    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);
    }

    int run(int source, int sink) {
        const auto [max_flow, min_cost] = min_cost_max_flow(source, sink);
        for (int i = 0; i < node_count; ++i) {
            for (unsigned int j = 0; j < adj[i].size(); ++j)
                delete adj[i][j];
            adj[i].clear();
        }

        return max_flow;
    }
};

void read() {
    cin >> N >> M >> K;
    G.resize(N + 1);
    for (int i = 0; i < M; ++i) {
        cin >> x >> y >> w;
        G[x].push_back({y, w});
    }

    int pathLength;
    vector<pair<int, int>> path;

    starts.resize(K);
    for (int i = 0; i < K; ++i) {
        cin >> starts[i];
    }

    for (int x = 0; x < K; ++x) {
        cin >> pathLength;
        path.resize(pathLength);

        for (int j = 0; j < pathLength; ++j) {
            cin >> y >> t;
            path[j] = {y, t};

        }

        paths.push_back(path);
    }
}

int IDX = 0;
vector<vector<int>> node_time; // nodes x TMAX
vector<vector<int>> node_time_double;
vector<int> targetIds;



MaxFlowMinCost *constructFlowGraph(int nodes, int max_edge) {

    node_time = vector<vector<int>>(N, vector<int>(TMAX + 5, -1));
    node_time_double = vector<vector<int>>(N, vector<int>(TMAX + 5, -1));
    targetIds = vector<int>(K + 1, -1);
    vector<vector<bool> >viz = vector<vector<bool>>(N, vector<bool>(TMAX + 5, false));

    IDX = -1;

    source = ++IDX; // 0
    sink = ++IDX; // 1

    // T1, T2, .., Tk -> nodes - k, nodes-k - 1, ..., nodes - k - (k + 1) = nodes - 1

    MaxFlowMinCost *maxFlowMinCost = new MaxFlowMinCost(nodes);

    queue<pair<int, int>> nodesInCurrT;

    for (int agentId = 0; agentId < K; ++agentId) { // First layer s -> agents & double it
        int agentNode = starts[agentId];
        node_time[agentNode][0] =  ++IDX;
        maxFlowMinCost->add_edge(source, node_time[agentNode][0], 1, 0);

        nodesInCurrT.push({agentNode, 0});
    }

   // dbg(nodesInCurrT.size()); // = K


    while (!nodesInCurrT.empty()) {

        const auto [currNode, currTime] = nodesInCurrT.front();
        nodesInCurrT.pop();

        if (currTime > max_edge || viz[currNode][currTime]) // skip
            continue;

        viz[currNode][currTime] = true;

        if (node_time_double[currNode][currTime] == -1)
            node_time_double[currNode][currTime] = ++IDX;

        maxFlowMinCost->add_edge(node_time[currNode][currTime], node_time_double[currNode][currTime], 1, 0); // Double node


        int currNodeFromId = node_time_double[currNode][currTime] ; // Now start to create edges out the DUPLICATED NODE

        // If agent waits in this node => add edge (node, i) -> (node, i + 1) w/ `w = 1 = (i + 1) - i`
        if (node_time[currNode][currTime + 1] == -1)
            node_time[currNode][currTime + 1] = ++IDX;
        maxFlowMinCost->add_edge(currNodeFromId, node_time[currNode][currTime + 1], 1, 1); // w = 1

        nodesInCurrT.push({currNode, currTime + 1}); // Agent waits - Add to queue only nodes that ARE NOT DUPLICATED

        for (const auto &[neigh, time]: G[currNode]) {
            if (time + currTime > max_edge)
                continue;
            if (node_time[neigh][time + currTime] == -1)
                node_time[neigh][time + currTime] = ++IDX;

            maxFlowMinCost->add_edge(currNodeFromId, node_time[neigh][time + currTime], 1, time);

           //dbg(currNode, neigh, time, time + currTime, currTime);

            nodesInCurrT.push({neigh, time + currTime});
        }
    }

//    dbg("step1 done");

    // T0, T1, .., T_{k - 1} -> nodes - k + 0, nodes - k + 1, ..., nodes - k + (k - 1) = nodes - 1
    // T_i = nodes - k + i
    // Add nodes to Targets (last layer)

    for (int targetId = 0; targetId < K; ++targetId) {
        for (const auto [targetNode, targetTime]: paths[targetId]) {
            //dbg(targetId, targetNode, targetTime);
            if (node_time_double[targetNode][targetTime] ==
                -1 || targetTime > max_edge) // skip, as this target cannot be caught at this specific time
                continue;

            if (targetIds[targetId] == -1)
                targetIds[targetId] = ++IDX;

            maxFlowMinCost->add_edge(node_time_double[targetNode][targetTime], targetIds[targetId], 1, 0);
            // dbg("yes", targetNode, targetTime);
        }
        int node = paths[targetId].back().first;
        for (int t = paths[targetId].back().second + 1; t <= max_edge; ++t) {
            if (node_time_double[node][t] ==
                -1) // skip, as this target cannot be caught at this specific time
                continue;

            if (targetIds[targetId] == -1)
                targetIds[targetId] = ++IDX;

            maxFlowMinCost->add_edge(node_time_double[node][t], targetIds[targetId], 1, 0);
        }
    }

    for (int targetId = 0; targetId < K; ++targetId) {
        if (targetIds[targetId] != -1)
            maxFlowMinCost->add_edge(targetIds[targetId], sink, 1, 0);
    }



    return maxFlowMinCost;

}

void solveMakeSpan() {

    int makeSpan = INT_MAX;
    int r = TMAX;
    int l = 0;

    while (l <= r) {
        int mid = (l + r) / 2;


        auto *maxFlowMinCost = constructFlowGraph(2 * N * TMAX + K + 2, mid);
        int max_flow = maxFlowMinCost->run(source, sink);
        delete maxFlowMinCost;

        // dbg(mid, max_flow);

        if (max_flow == K) { // Can match -> CUPLAJ
            makeSpan = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << makeSpan << '\n';
}



int main() {

//    freopen("./tests/mincost/xl-sparse-9.in", "r", stdin);
//    freopen("./tests/mincost/xl-sparse-9.out", "w", stdout);


    // NOTE: N <= 40; K <= 25
    read();

    solveMakeSpan();
    return 0;
}