Earliest Arrival with Limited Bus Transfers

You are given a graph with (n) nodes and (m) edges. The graph has no self‐loops or multiple edges. Each edge has a length. Node (1) represents the school, and node (n) represents home.\n\nThere are (s) bus routes. Each bus route is given as a sequence of distinct vertices; the bus stops at every vertex on its route (and never visits the same vertex twice). A bus traveling on an edge spends time exactly equal to the edge’s length. For each bus route, the service begins from its first stop at time (F) (the departure time of the first bus) and then buses depart periodically with an interval of (I) (i.e. departure times are (F, F+I, F+2I, \dots)). When a bus leaves its starting vertex at time (d), it reaches the stop at position (j) at time (d + D_j) where (D_j) is the sum of the lengths of edges from the first stop to the (j^{th}) stop along the route.\n\nAt time (t) you start at the school (node 1). You are allowed to take buses with at most (k) transfers (i.e. you may ride at most (k+1) bus rides). When you are at a stop, you may wait for a bus that passes through that stop. The waiting time is the difference between your arrival time at that stop and the time at which a bus on that route arrives at that stop. (There is no additional transfer time.)\n\nYour task is to determine the earliest time you can arrive at home (node (n)). Only the time spent riding buses and waiting for them is counted.\n\n

(\textbf{Input Format}:)\nThe first line contains seven integers: (n), (m), (s), (k), (t), (F), and (I) (the period interval).\n\nThe next (m) lines each contain three integers (u), (v), and (w), indicating an edge between (u) and (v) with length (w).\n\nThen (s) bus routes are given. For each bus route, the first number is an integer (c), denoting the number of stops on that route, followed by (c) integers representing the sequence of stops. It is guaranteed that for every consecutive pair of stops in a route, there is an edge between them in the graph.\n\n(\textbf{Output Format}:)\nOutput a single integer: the earliest time you can reach home. If it is impossible to reach home under the given conditions, output -1.\n\n(\textbf{Note}:) All formulas should be rendered in (\LaTeX) format.

inputFormat

The input begins with a line containing seven space-separated integers: (n) (m) (s) (k) (t) (F) (I).\n\nThen follow (m) lines, each with three integers (u), (v), and (w), representing an edge between nodes (u) and (v) with length (w).\n\nThis is followed by (s) groups. Each group begins with an integer (c) (the number of stops in the bus route) followed by (c) space-separated integers denoting the sequence of stops.

outputFormat

Output a single integer indicating the earliest time at which home (node (n)) can be reached. If home cannot be reached, output -1.

sample

5 6 2 1 0 0 10
1 2 5
2 3 5
3 5 5
1 4 10
4 5 5
2 5 20
4 1 2 3 5
3 1 4 5

15