#include<iostream.h>
#include<fstream.h>
int const inf=500;
ifstream f("graf.in");
ofstream g("graf.out");
int start,n,s[100],a[100][100],j,t[100],c[100];
void citire()
{f>>n>>start;
for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++) f>>a[i][j];

}
void dijkstra(int x)
{int i,min,ok,k;
for(i=1;i<=n;i++){ c[i]=a[x][i]; t[i]=x; s[i]=0; }
t[x]=0;
s[x]=1; ok=1;
for(j=1;j<=n-1;j++)
{ min=inf;
for(i=1;i<=n;i++) if(s[i]==0 && min>c[i]) {min=c[i]; k=i; };
 s[k]=1; 
	for(i=1;i<=n;i++) if(s[i]==0 && c[i]>c[k]+a[k][i]) { c[i]=c[k]+a[k][i]; t[i]=k; }
	
}
}
void drum(int i)
{if(t[i]!=0) drum(t[i]); g<<i<<' ';}
void afis(int x)
{for(int i=1;i<=n;i++)
if(i!=x) if(t[i]!=0) { g<<" drumul minim de la nodul "<<x<<" la nodul "<<i<<" are costul "<<c[i]<<'\n';
drum(i); g<<'\n'; }
else g<<"nu exista drum de la "<<x<<" la "<<i<<'\n'; }
int main()
{citire();
dijkstra(start);
for(int i=1;i<=n;i++) g<<i<<' ';
g<<'\n';
afis(start);
f.close();
return 0;
}