SP698 PLHOP - Plane Hopping

This man has grown so rich that, when he travels between any two locations he always takes atleast K flights. In a region of N cities, we need to find the minimal cost required for the man to travel between every pair of cities. There are provisions (especially for this type of rich men,) to fly from i-th city to the i-th city itself!

T – The number of test cases. In each test case : K N NxN matrix representing the costs of the tickets. The i-th line, j-th column’s entry represents the cost of a ticket from city i to city j. The numbers are of course space separated. **Constraints :** T

For the i-th test case , 1st line is of the form “Region #i:”. In the following N lines, output an NxN matrix where the j-th element of the i-th line represents the minimal cost to travel from city i to city j with taking atleast K flights. The numbers on a line must be separated by atleast one space. Output a blank line after each testcase (including the last one).