Teleport#328
Timur has decided to explore the universe. Fortunately for him, the universe is small and consists of planets. Travel between planets is made possible using parallel universes. For this, bidirectional portals connect certain pairs of planets, and on each planet there is at most one portal for each parallel universe. A transition between planets is instantaneous and free: the traveler enters the portal of the -th universe on planet , exits on planet using the same universe , and must take an aspirin tablet (even a brief stay in a parallel universe, due to the so-called "Bach effect", causes an unbearable headache). Moving between portals on the same planet requires travel by photon airships; ticket prices for such airships depend on the planet and the pair of portals used.
Timur starts at portal of planet , and needs to reach portal of planet , where his team is waiting. What is the minimum number of aspirins he needs to take and the minimum possible sum in tenge required for this journey? Timur prioritizes his health over wealth, so he prefers to minimize the number of aspirin tablets, even if he has to spend more money.
The first line contains integers: (number of planets), (number of interplanetary portals), and (number of parallel universes) (1 \leq n \leq 100, 1 \leq k \leq 11, 1 \leq m \leq 100000). Each of the next lines contains integers , , , describing a portal: planets and are connected by the portal (1 \leq a, b \leq n), and is the index of the parallel universe used by the portal (1 \leq c \leq k). After this, there are blocks of lines each, and each line contains integers: this part describes the routes of photon airships on each planet. The -th number of the -th line of the -th block is the price, in tenge, for an airship ticket from portal to portal on planet . Ticket prices are integers from to . Numbers in a line are separated by spaces.
Output two integers separated by a space: the minimum number of aspirin tablets, and the minimum possible amount of tenge needed for such a journey.
Example 1