#include <fstream>
#define INF 10001

using namespace std;

ifstream fin("bellman_ford.in");
ofstream fout("bellman_ford.out");

void citire();
//void dijkstra();
void bellman_ford();
void afisare();

int c[INF][INF];
int cmin[INF];
int tata[INF],M[INF];
int sol[INF];
int n,m,x0;

int main()
{
    citire();
    //dijkstra();
    bellman_ford();
    afisare();
    fout.close();
    return 0;
}

void citire()
{
    int i,j,x,y,z;
    fin>>n>>m>>x0; // citim nr de varfuri, de arce si varful de start

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
			// punem in toata matricea INF
            c[i][j]=INF;
    // punem pe diagonala principala 0
    for(i=1;i<=n;i++)
        c[i][i]=0;
    for(i=1;i<=m;i++)
    {
		// citim si punem costurile in matrice
        fin>>x>>y>>z;
        c[x][y]=z;
    }
}

/*void dijkstra()
{
   int i,j,min=0,co,x;
    M[x0]=1; //punem in M primul vf de start
    for(i=1;i<=n;i++)
    {
      cmin[i]=c[x0][i];
      if(i!=x0)//punem predecesorul daca exista
        tata[i]=x0;
      else
        tata[i]=0;
    }

   for(i=1;i<=n-1;i++)
   {
       min=0; co=INF;//determinam minimul dintre costuri si retinem si varful corespondent
       for(j=1;j<=n;j++)
       {
           if(M[j]==0 && cmin[j]<co)
           {
               min=j;
               co=cmin[j];
           }
       }

       M[min]=1;// adaugam in multimea varfurilor vizitate deja varful curent

       for(x=1;x<=n;x++)  //actualizam costurile daca exista o varianta mai buna
           if(M[x]==0 && cmin[x]>cmin[min]+c[min][x])
           {
               cmin[x]=cmin[min]+c[min][x];
               tata[x]=min; //retinem si predecesorul
           }
   }

}*/

void bellman_ford()
{
    int i, x, y, op;
    for(i=1; i<=nl i++)
    {
        op=0;

        for(x=1; x<=n; x++)
        {
            for(y=1; y<=n;i++)
                if(cmin[x]>cmin[min]+c[min][x])
                {
                    cmin[x]=cmin[min]+c[min][x];
                    tata[x]=min;
                    op=1;
                }
        }
    }

    if(op)
        {
            fout<<"nu exista solutie";
            fout.close();
        }
}

void afisare()
{
    int i,j,k;
    for(i=1;i<=n && i!=x0 ;i++)
        if(cmin[i]==INF && )//daca exista un circuit negativ in graf
            fout<<"Nu exista drum de la..";
        else
        {
            fout<<cmin[i]<<'\n';//afisam costul
            j=i;k=0;
            sol[++k]=j;
            while(j)
            {
                sol[++k]=tata[j];//retinem drumul
                j=tata[j];
            }
            for(j=k;j>0;j--)//redam drumul in sens invers
                fout<<sol[j]<<' ';
            fout<<'\n';
        }
}