AT_abc445_f [ABC445F] Exactly K Steps 2

頂点 $ 1, $ 頂点 $ 2,\ldots, $ 頂点 $ N $ の $ N $ 頂点からなる有向グラフがあります。 $ 1 $ 以上 $ N $ 以下の任意の整数の $ 2 $ つ組 $ (i,j) $ について、頂点 $ i $ から頂点 $ j $ への有向辺がちょうど $ 1 $ 本存在し、そのコストは $ C _ {i,j} $ です。 正整数 $ K $ が与えられます。 $ s=1,2,\ldots,N $ のそれぞれについて、以下の問題を解いてください。 - 頂点 $ s $ から出発し、辺に沿って移動することを $ K $ 回繰り返して頂点 $ s $ へ向かう方法のうち、通った辺のコストの総和としてありうる最小値を求めよ。厳密には、 $ v _ 0=v _ K=s $ を満たす $ 1 $ 以上 $ N $ 以下の整数からなる長さ $ K+1 $ の列 $ v=(v _ 0,v _ 1,\ldots,v _ K) $ に対する $ \displaystyle\sum _ {i=1} ^ {K}C _ {v _ {i-1},v _ i} $ の総和としてありうる最小値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ 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} $

$ N $ 行にわたって出力せよ。 $ i $ 行目 $ (1\le i\le N) $ には $ s=i $ に対する問題の答えを出力せよ。

### Sample Explanation 1 $ s=1 $ のとき、 $ 1\rightarrow2\rightarrow3\rightarrow1 $ と移動すると、通った辺のコストの総和は $ 1+2+5=8 $ となります。 頂点 $ 1 $ からスタートして $ 3 $ 回辺に沿って移動し、通った辺のコストの総和を $ 7 $ 以下にすることはできないため、 $ 1 $ 行目には `8` を出力してください。 $ s=4 $ のとき、 $ 4\rightarrow4\rightarrow4\rightarrow4 $ と移動すると、通った辺のコストの総和は $ 3+3+3=9 $ となります。 同じ辺や同じ頂点を複数回通ってもよいことと、同じ辺を複数回通った場合は通った回数だけ総和にその辺のコストが足されることに注意してください。 ### Sample Explanation 2 答えが $ 2 ^ {32} $ 以上になる場合があります。 ### Constraints - $ 1\le N\le100 $ - $ 1\le K\le10 ^ 9 $ - $ 0\le C _ {i,j}\le10 ^ 9\ (1\le i\le N,1\le j\le N) $ - 入力はすべて整数