AT_abc445_f [ABC445F] Exactly K Steps 2

There is a directed graph with $ N $ vertices, vertex $ 1, $ vertex $ 2,\ldots, $ vertex $ N $ . For any pair of integers $ (i,j) $ with $ 1 \leq i,j \leq N $ , there is exactly one directed edge from vertex $ i $ to vertex $ j $ with cost $ C_{i,j} $ . You are given a positive integer $ K $ . For each of $ s=1,2,\ldots,N $ , solve the following problem. - Among the ways to start at vertex $ s $ , move along an edge $ K $ times, and return to vertex $ s $ , find the minimum possible total cost of the edges traversed. More formally, find the minimum possible value of $ \displaystyle\sum_{i=1}^{K}C_{v_{i-1},v_i} $ for a sequence $ v=(v_0,v_1,\ldots,v_K) $ of integers between $ 1 $ and $ N $ , inclusive, of length $ K+1 $ satisfying $ v_0=v_K=s $ .

The input is given from Standard Input in the following format: > $ N $ $ K $ $ C_{1,1} $ $ C_{1,2} $ $ \ldots $ $ C_{1,N} $ $ C_{2,1} $ $ C_{2,2} $ $ \ldots $ $ C_{2,N} $ $ \vdots $ $ C_{N,1} $ $ C_{N,2} $ $ \ldots $ $ C_{N,N} $

Output $ N $ lines. The $ i $ -th line $ (1 \le i \le N) $ should contain the answer to the problem for $ s=i $ .

### Sample Explanation 1 For $ s=1 $ , moving $ 1\rightarrow2\rightarrow3\rightarrow1 $ gives a total cost of $ 1+2+5=8 $ . It is impossible to start at vertex $ 1 $ , move along an edge three times, and achieve a total cost of $ 7 $ or less, so print `8` on the first line. For $ s=4 $ , moving $ 4\rightarrow4\rightarrow4\rightarrow4 $ gives a total cost of $ 3+3+3=9 $ . Note that the same edge or the same vertex may be traversed multiple times, and if the same edge is traversed multiple times, its cost is added to the total that many times. ### Sample Explanation 2 The answer may be $ 2^{32} $ or greater. ### Constraints - $ 1 \le N \le 100 $ - $ 1 \le K \le 10^9 $ - $ 0 \le C_{i,j} \le 10^9\ (1 \le i \le N,1 \le j \le N) $ - All input values are integers.