#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);
}
#define debug if (n==850)

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	int n; cin>>n;
	vector<vector<int> > a(n,vector<int>(n));
	rep(i,0,n-1) rep(j,0,n-1) cin>>a[i][j];

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

	vector<int> freq(n);
	vector<int> ans(n+1,inf);
	auto solve=[&](int st)
	{
		vector<vector<int> > f(n,vector<int>(n+1,inf));
		vector<vector<int> > pre(n,vector<int>(n,-1));

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

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

	mt19937 rng(3068863558);
	int T=10;
	rep(i,1,T)
	{
		int x=rng()%n;
		debug printf("x %d\n",x);
		solve(x);
		return 0;
	}
	debug printf("here ok\n");
	debug return 0;

	vector<int> ord(n);
	rep(i,0,n-1) ord[i]=i;
	sort(ord.begin(),ord.end(),[&](auto x,auto y){return freq[x]>freq[y];});
	rep(i,0,min(T,n)-1)
	{
		solve(ord[i]);
	}

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

	return 0;
}