#include <bits/stdc++.h>;
 using namespace std;
 ifstream cin("traseu.in");
 ofstream cout("traseu.out");
const pinf=1000;  
int a[pinf][pinf],n,m;
 
 
void citire_cost()
{fstream f;
 int i,j,x,y,c;
 f.open("roy.in",ios::in);
 f>>n>>m;
 for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      if(i==j)
             a[i][j]=0;
       else
             a[i][j]=pinf;
  for(i=1;i<=m;i++)
     {f>>x>>y>>c;
      a[x][y]=a[y][x]=c;}
}
 
void afisare_mat()
{for(int i=1;i<=n;i++)
   {for(int j=1;j<=n;j++)
             if(a[i][j]==pinf)
                cout<<"pinf ";
             else
               cout<<a[i][j]<<"  ";
    cout<<endl;}
}
 
void genarare_matrice_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 descompun_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])
                           {descompun_drum(i,k);
                            descompun_drum(k,j);
                            g=1;}
              k++;
              }
  if(!g)
     cout<<j<<" ";  
 
}
 
void scriu_drum(int nodini,int nodfin)
{if(a[nodini][nodfin]<pinf)
     {cout<<a[nodini][nodfin];
      cout<<endl;
      cout<<nodini<<" ";
      descompun_drum(nodini,nodfin); 
     }
 else
     cout<<0;
}
 
 
void main()
{clrscr();int x,y;
citire_cost();
afisare_mat();
genarare_matrice_drumuri_optime();
afisare_mat();
cin>>x;
cin>>y;
scriu_drum(x,y);
getch();
}