#include <iostream>
using namespace std;
int n;
float m[50][50];
void drum(int i, int j){
int k=1, gasit=0;
while((k<=n) && !gasit){
if((i!=k) && (j!=k) && (m[i][j]==m[i][k]+m[k][j])){
drum(i,k);drum(k,j);
gasit=1;
}
k++;
}
if (!gasit) cout<<j<<" ";
}
int main(){
int i,j,k,ni,nf;
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>m[i][j];
for(i=1;i<=n;i++){
for(j=1;j<=n;j++) if(m[i][j]>1.e+19)cout<<"ì ";else cout<<m[i][j]<<" ";
cout<<endl;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(m[i][j]>m[i][k]+m[k][j]) m[i][j]=m[i][k]+m[k][j];
cout<<endl<<endl;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++) if(m[i][j]>1.e+19)cout<<"ì ";else cout<<m[i][j]<<" ";
cout<<endl;
}
cout<<endl<<endl;
cout<<"nodul initial ";cin>>ni;
cout<<"nodul final ";cin>>nf;
cout<<endl;
if(m[ni][nf]<1.e20){
cout<<"drumul minim este: "<<endl;
cout<<ni<<" ";
drum(ni,nf);}
else cout<<"nu exista drum de la "<<ni<<" la "<<nf;
cout<<endl;
return 0;
}
