N,M=map(int,input().split())
T=list(map(int,input().split()))
result=T[:]
A=[list(map(int,input().split())) for i in range(N)]
v=[[[0]*N for i in range(N)] for k in range(60)]
for i in range(N):
  for j in range(N):
    v[0][i][j]=A[i][j]
for k in range(1,60):
  for i in range(N):
    for j in range(N):
      ans=0
      for w in range(N):
        ans=max(ans,v[k-1][i][w]+v[k-1][w][j])
      v[k][i][j]=ans
result=[0]*N
B=-1
for k in range(60):
  if (M>>k)&1:
    if B==-1:
      B=[[0]*N for i in range(N)]
      for i in range(N):
        B[i]=v[k][i][:]
    else:
      B2=[[0]*N for i in range(N)]
      for i in range(N):
        for j in range(N):
          ans=0
          for w in range(N):
            ans=max(ans,B[i][w]+v[k][w][j])
          B2[i][j]=ans
      for i in range(N):
        B[i]=B2[i][:]
result=[0]*N
for i in range(N):
  for j in range(N):
    result[j]=max(result[j],T[i]+B[i][j])
print(*result)