#include <fstream>
using namespace std;
#define MAX 100
#define INF 32000

int n, m;
int d[MAX], s[MAX];
int a[MAX][MAX];
int t[MAX];

void Dijkstra(int sursa);

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

int main()
{
    fin >> n >> m >> s;
    int x, y, c;
    for ( int i = 1; i <= n; i++ )
    {
        c[i][i] = 0;
        for ( int j = i + 1; j <= n; j++ )
        {
            c[i][j] = INF;
            c[j][i] = INF;
        }
    }
    for ( int i = 0; i < m; i++ )
    {
        fin >> x >> y >> c;
        a[x][y] = c;
        a[y][x] = c;
    }
    
    Dijkstra(s);
    
    for ( int i = 1; i <= n; i++ )
    {
        fout << d[i] << " ";
    }
    
    fin.close();
    fout.close();
    
    return 0;
}

void Dijkstra(int sursa)
{
     d[sursa] = 0;
     s[sursa] = 1;
     t[sursa] = 0;
     
     int min = INF;
     for ( int p = 1; p < n; p++ )
     {
         min = INF;
         int k = 0;
         for ( int i = 1; i <= n; i++ )
         {
             if ( !s[i] && d[i] < min )
             {
                  min = d[i];
                  k = i;
             }
         }
         s[k] = 1;
         for ( int i = 1; i <= n; i++ )
         {
             if ( !s[i] && d[i] > d[k] + c[k][i] )
             {
                  d[i] = d[k] + c[k][i];
                  t[i] = k;
             }
         }
     }
}