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

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

    long long N,M; cin >> N >> M;
    vector<int> T(N);
    for(auto &t : T) cin >> t;
    vector<vector<int>> A(N,vector<int>(N));
    for(auto &h : A) for(auto &w : h) cin >> w;

    int n = 1500;
    vector<vector<int>> day(n+1,vector<int>(N)),OK = day;
    day.at(0) = T;
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>> Q;
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            if(i == k) continue;
            Q.push({T.at(i)+A.at(i).at(k),1,k});
        }
    } 
    while(Q.size()){
        auto [d,let,pos] = Q.top(); Q.pop();
        if(let == n+1) break;
        OK.at(let).at(pos)++;
        if(OK.at(let).at(pos) == N-1){
            if(day.at(let-1).at(pos) > d){
                OK.at(let).at(pos)--;
                Q.push({day.at(let-1).at(pos),let,pos}); continue;                
            }
            day.at(let).at(pos) = d;
            for(int to=0; to<N; to++) if(to != pos) Q.push({d+A.at(pos).at(to),let+1,to});
        }
    }
    for(int i=0; i<N; i++){
        if(M > n){
            long long d1 = day.at(n).at(i),d2 = day.at(n-1).at(i);
            long long more = M-n,d = d1-d2;
            cout << more*d+d1 << " ";
        }
        else cout << day.at(M).at(i) << " ";
        
    }
    cout << endl;
}