#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n;
int c[855][855],ord[855];
mt19937 rnd(0);

int a[855][855],dp[855][855],ans[855];
void solve(int p){//强制以 p 位置作为开始
	int cur = p,K = 0;
	while(1){
		rep(i,1,n) a[K][i] = c[cur][i];
		cur++;K++;
		cur %= n;
		if(cur == p) break;
	}
	rep(i,0,n - 1){
		fill(dp[i],dp[i] + n + 1,inf);
		rep(j,0,i){
			int delta = a[j][i - j + 1];
			chkmin(dp[i][1],delta);
			rep(k,2,j + 1) chkmin(dp[i][k],dp[j - 1][k - 1] + delta);
		}
	}
	rep(k,1,n) chkmin(ans[k],dp[n - 1][k]);
}

const int lim = 50;
void solve2(int p){
	int cur = p,K = 0;
	while(1){
		rep(i,1,n) a[K][i] = c[cur][i];
		cur++;K++;
		cur %= n;
		if(cur == p) break;
	}
	rep(i,0,n - 1){
		fill(dp[i],dp[i] + lim + 1,inf);
		rep(j,0,i){
			int delta = a[j][i - j + 1];
			chkmin(dp[i][1],delta);
			rep(k,2,min(j + 1,lim)) chkmin(dp[i][k],dp[j - 1][k - 1] + delta);
		}
	}
	rep(k,1,lim) chkmin(ans[k],dp[n - 1][k]);		
}

int main(){
	scanf("%d",&n);
	rep(i,0,n - 1){
		rep(j,1,n) scanf("%d",&c[i][j]);
	}
	rep(i,0,n - 1) ord[i] = i;
	rep(i,0,n - 1) swap(ord[i],ord[rnd() % (i + 1)]);
	fill(ans,ans + n + 1,inf);

	rep(i,0,lim) solve(ord[i]);
	rep(i,0,n - 1) solve2(i);
	rep(i,1,n) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}