# include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int INF=2147483647;
int n,m,i,x,y,c,d[50001],t[50001],a[50001][100],w[50001][10000];
void read()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
         {
          f>>x>>y>>c;
          a[x][++a[x][0]]=y;
          w[x][y]=c;
         }
    f>>x>>y;
}
void dijkstra()
{
    int z,mini=INF;
    bool b[50001];
    for(i=1;i<=n;i++)
        {
         b[i]=0;
         if(w[x][i])
            {
             d[i]=w[x][i];
             t[i]=x;
            }
         else
           d[i]=INF;
         if(d[i]<mini)
             {
              mini=d[i];
              z=i;
             }
        }
    d[x]=0;
    b[x]=1;
    while(mini!=INF)
           {
            b[z]=1;
            if(z==y)
                break;
            for(i=1;i<=a[z][0];i++)
                  if(d[a[z][i]]>d[z]+w[z][a[z][i]])
                     {
                      d[a[z][i]]=d[z]+w[z][a[z][i]];
                      t[a[z][i]]=z;
                     }
            mini=INF;
            for(i=2;i<=n;i++)
                 if(!b[i]&&d[i]<mini)
                     {
                      mini=d[i];
                      z=i;
                     }
           }
}
void write()
{
    g<<d[y]<<'\n';
    while(t[y])
          {
           g<<t[y]<<" ";
           y=t[y];
          }
}
void infoarena()
{
    for(i=2;i<=n;i++)
         if(d[i]!=INF)g<<d[i]<<" ";
         else g<<"0 ";
}
int main()
{
    read();
    x=1;
    y=0;
    dijkstra();
    //write();
    infoarena();
    f.close();
    g.close();
    return 0;
}