Hexer's Journey

Byteasar, now a hexer (monster slayer), must return to his hometown Byteburg. The land between is filled with monsters and towns. Roads connect these towns (roads do not cross outside towns) and each road may host a certain type of monster. Fortunately, some towns have blacksmiths who forge special swords effective against specific monster types.

Byteasar starts at town 1 without any sword (although town 1 may provide one) and wants to reach town n in the shortest possible time. However, he must be prepared: before traversing any road where a monster of type \( m \) might appear, he must have already visited a town that forges a sword effective against that monster (i.e. he must have acquired sword type \( m \)).

The land is described as follows:

• The first line contains three integers \( n, m, k \) — the number of towns, the number of roads, and the total number of monster types respectively.
• The next \( n \) lines describe the towns. Each line starts with an integer \( r \) denoting the number of sword types available in that town. Following that are \( r \) integers, each representing a monster type for which a sword is available in that town.
• The next \( m \) lines describe the roads. Each road is given by four integers \( u, v, t, d \) meaning there is a bidirectional road between towns \( u \) and \( v \) that takes \( t \) units of time to travel and on which a monster of type \( d \) might appear. To safely travel this road, Byteasar must already have a sword effective against monster type \( d \) prior to entering the road.

Your task is to compute the minimum travel time for Byteasar to reach town \( n \) from town 1 while ensuring that, for every road you traverse, if a monster of type \( d \) is present then you have already acquired the corresponding sword. If it is impossible to reach town \( n \) under these conditions, output -1.

Note: Byteasar can carry an unlimited number of swords, and obtaining a sword in a town is instantaneous.

inputFormat

The input begins with a line containing three integers \( n, m, k \) separated by spaces.

The next \( n \) lines describe each town. The \( i \)-th line starts with an integer \( r_i \) (the number of sword types available in town \( i \)), followed by \( r_i \) integers representing the monster types for which a sword is available in that town.

The following \( m \) lines each contain four integers \( u, v, t, d \) describing a bidirectional road between towns \( u \) and \( v \) that takes \( t \) time units and may have monsters of type \( d \) encountered along it.

outputFormat

Output a single integer: the minimum travel time needed for Byteasar to reach town \( n \) with the proper swords to combat any encountered monsters. If no valid route exists, output -1.

sample

4 4 3
1 1
1 2
1 3
0
1 2 5 1
2 3 5 2
1 3 15 2
3 4 10 3

20