// Algoritmul lui Dijkstra O (n^2)
#include <cstdio>
#include <fstream>

using namespace std;

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define MAX_N 100
#define INF 0x3f3f3f3f

int A[MAX_N][MAX_N];
int D[MAX_N];
int S[MAX_N];
int T[MAX_N];

int N, M, R, i;

    void matpond ( void )
    {
         int i, j, x, y, c;
         for ( i = 1; i <= N; ++i)
             for ( j = 1; j <= N; ++j)
                 if (i != j) A[i][j] = INF;
                 
         for ( i = 1; i <= M; ++i)
         {
             scanf ("%d %d %d", &x, &y, &c);
             A[x][y] = c;
         }        
    }
    
    void way (int c)
    
    {
         if (T[c]) way (T[c]);
         printf ("%d ", c);
    }
    
    void dijkstra ( void )
    {
         int min, pz, j;
         memset (S, 0, sizeof (S));
         S[R] = 1;
         for ( i = 1; i <= N; ++i)
         {
             D[i] = A[R][i];
             if (D[i] < INF && R != i) T[i] = R;
         }
         
         for ( i = 1; i <= N - 1; ++i)
         {
             min = INF;
             for ( j = 1; j <= N; ++j)
                 if ( !S[j] && D[j] < min)
                  {
                        min = D[j]; pz = j;
                  }
             S[pz] = 1;
             for ( j = 1; j <= N; ++j)
                 if (!S[j] && D[j] > D[pz] + A[pz][j])
                    {
                           D[j] = D[pz] + A[pz][j];
                           T[j] = pz;
                    }
         }
         for ( i = 1; i <= N; ++i)
             if (i != R && T[i] != 0) 
             {
                   printf ("%d ", D[i]);
                 //  way (i);
                 //  printf ("\n");
             }
             
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d %d", &N, &M, &R);
        matpond ();
        
        dijkstra ();
        
        return 0;
    }