#include <iostream.h>
#include <fstream.h>
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,s[5000],min,t[5000],a[5000][5000],k,d[5000],nod;

void drum(int i)
{if (t[i]!=0) drum(t[i]);
 fout<<i<<" ";
}



int main()
{int i,j,c,r;
 fin>>n>>k;
 while(fin>>i>>j>>c)
  a[i][j]=a[j][i]=c;


  for (i=1;i<=n;i++)
   for (j=1;j<=n;j++)
    if (i!=j && a[i][j]==0)
     a[i][j]=32000;

 for (i=1;i<=n;i++)
  {d[i]=a[i][k];
   t[i]=1;

   }

  t[k]=0;
  s[k]=1;

for (r=1;r<n;r++)
{min=30000;
 for (i=1;i<=n;i++)
  if (!s[i] && min>d[i])
    {nod=i;
     min=d[i];
    }

  s[nod]=1;

 for (i=1;i<=n;i++)
  if (!s[i] && d[i]>d[nod]+a[nod][i])
   {d[i]=d[nod]+a[nod][i];
    t[i]=nod;
   }

   }

for (i=1;i<=n;i++)
if (i!=k)
 {drum(i);
  fout<<d[i]<<endl;
 }



fout.close();
return 0;
}