#include<iostream.h>
#include<fstream.h>
#define inf 0x3fffffff
ifstream f("graf.in");
int start,n,s[100],a[100][100],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;
while(ok){ min=inf;
for(i=i;i<=n;i++) if(s[i]==0 && min>c[i]) {min=c[i]; k=i; };
if(min!=inf) {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;} }
	else ok=0;
};
}
void afis(int x[], int l)
{for(int i=1;i<=l;i++) cout<<x[i]<<' ';
cout<<'\n';
}
int main()
{citire();
dijkstra(start);
for(int i=1;i<=n;i++) cout<<i<<' ';
cout<<'\n';
afis(s,n); afis(c,n); afis(t,n);
f.close();
return 0;
}