ABC-445 F

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll mod = 1e9+7;

struct Matrix{
    ll n;
    vector<vector<ll>> mat;
    Matrix(int n) : n(n), mat(n, vector<ll>(n, LLONG_MAX)) {}

    // Matrix multiplication [modified]
    // C = A*B
    // original ->  c[i][j] = sum over k (a[i][k] * b[k][j])
    // chaned to -> c[i][j] = min over k (a[i][k] + b[k][j]) 
    Matrix operator*(const Matrix& other) const {
        Matrix ans(n);
        for (ll i = 0; i < n; i++){
            for (ll k = 0; k < n; k++){
                if (mat[i][k] == LLONG_MAX) continue;
                for (ll j = 0; j < n; j++){
                    if (other.mat[k][j] == LLONG_MAX) continue;
                    ans.mat[i][j] = min(ans.mat[i][j], mat[i][k] + other.mat[k][j]);
                }
            }
        }
        return ans;
    }
    // TC -> O(N^3)
    // SC -> O(N^2)
};

// matrix expo -> operation O(lg k) times
Matrix matExpETF(Matrix a, ll b, ll n){
    Matrix ans(n);
    for (ll i = 0; i < n; i++) ans.mat[i][i] = 0;
    while(b){
        if (b&1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

void solve(){
    ll n, k; cin >> n >> k;
    Matrix c(n);
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < n; j++){
            cin >> c.mat[i][j];
        }
    }

    // C^k[i][j] -> min cost to go from i to j in k moves
    Matrix ans = matExpETF(c, k, n);
    for (ll i = 0; i < n; i++) cout << ans.mat[i][i] << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    ll t = 1;
    while (t--) solve();
}

// TC -> O(N^3 lg k)
// SC -> O(N^2)