//Author Antonio-Gabriel Sturzu

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define inf 50000001


int main()
{
	int d[10005],min,**mat,i,j,n,nod;
	char viz[10005];
	clock_t start,stop;
	FILE *f=fopen("dijkstra.in","r");

	fscanf(f,"%i",&n);
	mat=(int **) calloc(n*n,sizeof(int *));
	for(i=0;i<n;i++)
		mat[i]=(int *) calloc(n,sizeof(int));

	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			fscanf(f,"%i",&mat[i][j]);
	fclose(f);

	memset(viz,0,sizeof(viz));
	start=clock();
	d[0]=0;
	for(i=1;i<n;i++)
		d[i]=inf;

	for(;;)
	{
		min=inf;
		for(i=0;i<n;i++)
		{
			if(viz[i]==0 && d[i]<min)
			{
				min=d[i];
				nod=i;
			}
		}
		if(min==inf)
			break;
		viz[nod]=1;

		for(i=0;i<n;i++)
		{
			if(mat[nod][i]+d[nod]<d[i] && mat[nod][i]!=-1)
				d[i]=mat[nod][i]+d[nod];
		}
	}
	stop=clock();
	printf("Au trecut %f secunde",(double)(stop-start)/CLOCKS_PER_SEC);

	f=fopen("dijkstra.out","w");
	for(i=1;i<n;i++)
	{
		if(d[i]==inf)
			d[i]=0;
		fprintf(f,"%i ",d[i]);
	}
	fprintf(f,"%s","\n");
	fclose(f);
	for(i=0;i<n;i++)
		free(mat[i]);
	free(mat);
	return 0;
}