#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;

int a[20][20],n;
#define pinfinit 1000000
void citire_cost()
{ifstream f("ro.in");
 int i,j,c;
  f>>n;
 for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      if(i==j)
             a[i][j]=0;
       else
             a[i][j]=pinfinit;

     while(f>>i>>j>>c)
      a[i][j]=a[j][i]=c;}


void afisare_mat()

{for(int i=1;i<=n;i++)
   {for(int j=1;j<=n;j++)
             if(a[i][j]==pinfinit)
                cout<<setw(10)<<"pinfinit";
             else
               cout<<setw(10)<<a[i][j];

    cout<<endl;}
}

void drumuri_optime()
{for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
               if(a[i][j]>a[i][k]+a[k][j])
                              a[i][j]=a[i][k]+a[k][j];
}

void drum(int i,int j)
{int g=0,k=1;
 while(k<=n&&!g)
{if(i!=k&&j!=k)
if(a[i][j]==a[i][k]+a[k][j])
{drum(i,k);
drum(k,j);
g=1;}
k++;
}
  if(!g)
     cout<<j<<" ";
}
void scriu_drum(int x,int y)
{if(a[x][y]<pinfinit)
     {cout<<"drumul de la "<<x<<" la "<<y<<" are lungimea "<<a[x][y];
      cout<<endl<<"un drum optim este: "<<endl;
      cout<<x<<" ";
      drum(x,y);
     }
 else
     cout<<"nu exista drum de la "<<x<<" la "<<y;

}

int main()
{int x,y;
citire_cost();
cout<<endl<<"matricea ponderilor "<<endl;
afisare_mat();
drumuri_optime();
cout<<endl<<"matricea drumurilor optime "<<endl;
afisare_mat();
cout<<endl<<"Se determina drumul minim intre varfurile x si y "<<endl;
cout<<"x=";cin>>x;
cout<<"y=";cin>>y;
scriu_drum(x,y);
return 0;

}