#include <iostream>
#include<bits/stdc++.h>
#define inf INT_MAX;
using namespace std;
int dist[100];
int viz[100];
int tata[100];
typedef struct
  {
      int j,c;
  }Tvecin;
vector< Tvecin > vecini[100];
queue<int> coada;
int n,m;
ifstream f("Date.in");

void citire()
  {
      f>>n>>m;
      for(int i=1;i<=m;i++)
      {
          Tvecin y;
          int x;
          f>>x>>y.j>>y.c;
          vecini[x].push_back(y);
      }
  }
  void formare_drum(int start)
     {
         if(tata[start])
            formare_drum(tata[start]);
         cout<<start<<" ";
     }
  int Belman_Ford(int start)
     {
          for(int i=1;i<=n;i++)
             dist[i]=INT_MAX;
         coada.push(start);
         dist[start]=0;
         tata[start]=0;
         int k;
         coada.push(start);
         while(!coada.empty())
         {
             k=coada.front();
             coada.pop();
             viz[k]++;
             if(viz[k]==n)
                 return 1;
             for(int i=0;i<vecini[k].size();i++)
             {
                 if(dist[vecini[k][i].j]>dist[k]+vecini[k][i].c)
                      {
                          dist[vecini[k][i].j]=dist[k]+vecini[k][i].c;
                          coada.push(vecini[k][i].j);
                          tata[vecini[k][i].j]=k;
                      }
             }
         }
         return 0;
     }
     void afiseaza_distante()
        {
            for(int i=1;i<=n;i++)
                if(dist[i]==INT_MAX)
                    cout<<"-"<<" ";
                  else cout<<dist[i]<<" ";
            cout<<endl;
        }


int main()
{
   citire();
   int s;
   f>>s;
   if(Belman_Ford(s)==0)
   {
       afiseaza_distante();
       for(int i=1;i<=n;i++)
          {
               if(tata[i])
                 formare_drum(i);
                else cout<<"Nu exista drum";
               cout<<endl;
          }
   }
}