#include <iostream>
#include<fstream>
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
int a[3001][3001],d[3001],s[3001],p[3001],n,m,x,y;
int const MAX=5000;
void citire() {int i,j,xx,yy,c;
f>>x;
f>>y;
for(i=1;i<=m;i++)
{

    f>>xx>>yy>>c;
    a[xx][yy]=a[yy][xx]=c;
}
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(i!=j&&a[i][j]==0)
    a[i][j]=a[j][i]=MAX;
}
void generare_drum(int x) {
int i,j,minim,y;
s[x]=1;
for(i=1;i<=n;i++) {
    d[i]=a[x][i];
    if(i!=x&&d[i]<MAX) p[i]=x; }
    for(i=1;i<=n-1;i++) {
        for(j=1,minim=MAX;j<=n;j++)
        if(s[j]==0&&d[j]<minim) {
           minim=d[j];
           y=j;
           }
           s[y]=1;
           for(j=1;j<=n;j++)
           if(s[j]==0&&d[j]>d[y]+a[y][j]) { d[j]=d[y]+a[y][j];
           p[j]=y;}
    }
}
void drum(int i) {
if(p[i]!=0) drum(p[i]); cout<<i<<" ";
}

int main()
{ int i;
f>>n>>m;
citire();
generare_drum(x);
g<<d[i];
}