Delivery Optimization

You are given a city represented as an undirected weighted graph with n intersections and m streets. There are k delivery vehicles. Each vehicle is described by a list of integers:

• s_i: the starting intersection.
• b_i: the battery capacity (unused in the simplified model).
• c_i: the number of charging stations in the route.
• p_i: the number of delivery destinations.
• Followed by c_i integers representing the charging station intersections (not used in route computation) and then p_i integers representing the delivery destinations.

Even though battery details and charging stations are provided, for this problem you may assume that each vehicle can travel unlimited distance. The delivery time for a vehicle is computed by summing up the shortest path distance from its current location to the next delivery destination, starting from s_i and updating the location after each delivery.

Your task is to compute the total minimum travel time required for all vehicles to deliver their packages.

The shortest paths between intersections should be computed using Dijkstra's algorithm. Formally, if you denote the shortest path distance between two intersections u and v as \(d(u,v)\), then for a vehicle with starting point \(s\) and delivery destinations \(d_1, d_2, \dots, d_p\), its travel time is:

\[ T = d(s, d_1) + d(d_1, d_2) + \cdots + d(d_{p-1}, d_p). \]

The answer is the sum of travel times for all vehicles.

inputFormat

The first line contains three space-separated integers: n (number of intersections), m (number of streets), and k (number of delivery vehicles).

Then m lines follow, each containing three space-separated integers u, v, w, representing a street between intersections u and v with travel time w.

Then k lines follow, each representing a vehicle. Each vehicle line starts with four integers: s_i (starting intersection), b_i (battery capacity), c_i (number of charging stations), and p_i (number of delivery destinations), followed by c_i + p_i integers. The first c_i of these are the intersections of available charging stations and the next p_i are the delivery destinations.

All input is given via standard input (stdin).

outputFormat

Output a single integer: the total minimum travel time required for all delivery vehicles to deliver all packages. The answer should be printed to standard output (stdout).

## sample

5 6 2
1 2 2
2 3 2
3 4 2
4 5 2
1 5 10
2 4 10
1 5 1 2 2 3
3 7 1 2 4 2 3

8