#include<bits/stdc++.h>
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
template <typename _Tp>void read(_Tp &x){
	char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
	x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
	if(f)x=-x;
}
template <typename _Tp,typename... Args>void read(_Tp &t,Args &...args){read(t);read(args...);}
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template <typename _Tp>inline void chmin(_Tp &a,const _Tp &b){a=a<b?a:b;}
const int N=855,inf=0x3f3f3f3f;
int c[N][N],ans[N],n,f[N][N],p[N];
void solve(int k,int x){
	int m=0;for(int i=x;i<=n;++i)p[++m]=i;
	for(int i=1;i<x;++i)p[++m]=i;
	for(int i=1;i<=n+1;++i)memset(f[i],63,(k+1)<<2);
	f[1][0]=0;
	for(int i=1;i<=n;++i){
		int o=p[i];
		for(int j=1;i+j<=n+1;++j)for(int t=0;t<k;++t){
			chmin(f[i+j][t+1],f[i][t]+c[o][j]);
		}
	}
	for(int i=1;i<=k;++i)chmin(ans[i],f[n+1][i]);
}
int main(){
	read(n);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)read(c[i][j]);
	memset(ans,63,sizeof(ans));
	for(int i=n;i>=1;--i){
		int T=(1.0*n/i-(i==n?0:1.0*n/(i+1)))*20;
		while(T--)solve(i,rnd()%n+1);
	}
	for(int i=1;i<=n;++i)printf("%d%c",ans[i]," \n"[i==n]);
	return 0;
}