Teleport
Timur has embarked on a journey to explore the universe, which, to his advantage, is quite small and consists of n planets. Travel between these planets is facilitated by k parallel universes. Each universe has bidirectional portals connecting certain pairs of planets. On any given planet, there is at most one portal for each parallel universe. Traveling through these portals is instantaneous and free of charge: Timur enters the portal of the i-th universe on planet a and exits on planet b. However, due to the "Bach effect," even a brief stay in a parallel universe results in severe headaches, necessitating an aspirin tablet. Moving between portals on the same planet requires the use of photon airships, with unique ticket prices for each pair of portals.
Timur starts his journey at portal 1 on planet 1 and needs to reach portal k on planet n, where his team is waiting. Your task is to determine the minimum number of aspirin tablets he needs and the total amount of money he should carry for the journey. Timur prioritizes his health over financial concerns, so he prefers to minimize the number of aspirin tablets, even if it means spending more money.
Input
The first line contains 3 integers: n - the number of planets, m - the number of portals between planets, and k - the number of parallel universes (1 ≤ n ≤ 100, 1 ≤ k ≤ 11, 1 ≤ m ≤ 100000). Each of the following m lines contains 3 integers a, b, c, describing an interplanetary portal: a and b are the planets connected by the portal (1 ≤ a, b ≤ n), and c is the number of the parallel universe used by the portal (1 ≤ c ≤ k). After this, there are n blocks of k lines each, where each line contains k integers. These describe the photon airship routes on each planet. The k-th element of the j-th line of the i-th block is the ticket price in tenge for traveling from portal j to portal k on planet i. The costs are integers ranging from 1 to 100. Numbers in the lines are separated by spaces.
Output
Output two integers separated by a space: the minimum number of aspirin tablets and the minimum possible sum in tenge.