#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define drep(i,a,b) for (int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;

const int inf=1e9;
inline bool chkmin(int &x,int y)
{
	return (x>y?x=y,1:0);
}

mt19937 rng(3068863558);
inline int rnd(int l,int r){return l+(rng()%(r-l+1));}

int main()
{
	clock_t clk=clock();
	ios::sync_with_stdio(false); cin.tie(0);

	int n; cin>>n;
	// int n=850;
	vector<vector<int> > a(n,vector<int>(n));
	rep(i,0,n-1) rep(j,0,n-1) cin>>a[i][j];
	// rep(i,0,n-1) rep(j,0,n-1) a[i][j]=rnd(1,100000);

	auto norm=[&](int x){return (x+100*n)%n;};

	vector<int> freq(n);
	vector<int> ans(n+1,inf);
	vector<int> mx(n);
	vector<vector<int> > f(n,vector<int>(n+1,inf));
	vector<vector<int> > pre(n,vector<int>(n+1,-1));

	auto solve=[&](int st,int top)
	{
		if (mx[st]>top) return;
		mx[st]=top;

		rep(i,0,n-1) rep(j,0,top) f[i][j]=inf;
		rep(i,0,n-1)
		{
			f[i][1]=a[norm(st)][i];
			pre[i][1]=-1;
			if (i!=n-1)
			{
				rep(j,1,top-1) if (f[i][j]<inf)
				{
					rep(k,i+1,n-1)
					{
						if (chkmin(f[k][j+1],f[i][j]+a[norm(st+i+1)][k-(i+1)]))
						{
							pre[k][j+1]=i;
						}
					}
				}
			}
		}

		rep(i,1,top)
		{
			int now=n-1;
			drep(j,i,1)
			{
				freq[norm(now+1)]++;
				now=pre[now][j];
			}
			chkmin(ans[i],f[n-1][i]);
		}
	};

	vector<int> ord(n);
	rep(i,0,n-1) ord[i]=i;

	drep(k,n,1)
	{
		if (k!=n&&((n/k)==(n/(k+1)))&&rnd(0,40)!=0) continue;
		rep(i,0,n-1) freq[i]=0;
		shuffle(ord.begin(),ord.end(),rng);
		int t=min(n,n/k/30+2);
		rep(i,0,t-1) solve(ord[i],k);
		cerr<<k<<"\n";

		// sort(ord.begin(),ord.end(),[&](auto x,auto y){return freq[x]>freq[y];});
		// rep(i,0,t-1) solve(ord[i],k);
	}

	rep(i,1,n) printf("%d ",ans[i]);
	printf("\n");

	return 0;
}