#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>

#define INF 0x3f3f3f3f

int n, m, s;
int e[10005][10005];
int vis[10005];
int dist[10005];

void dijkstra(int startx)
{

    for (int i = 1; i <= n; i++)
    {
        dist[i] = e[startx][i];
    }

    dist[startx] = 0;
    vis[startx] = 1;

    for (int i = 1; i <= n; i++)
    {
        int k, minNum = INF;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && dist[j] < minNum)
            {
                minNum = dist[j];
                k = j;
            }
        }

        vis[k] = 1;

        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && e[k][j] < INF)
            {
                if (dist[k]+e[k][j] < dist[j])
                {
                    dist[j] = dist[k]+e[k][j];
                }
            }
        }
    }
}

int main()
{
    int u, v, w;
    cin>>n>>m>>s;

    for (int i = 0; i <= n; i++)
    {
        dist[i] = INF;
        for (int j = 0; j <= n; j++)
        {
            e[i][j] = INF;
            e[j][i] = INF;
        }
    }

    for (int i = 0; i < m; i++)
    {
        cin>>u>>v>>w;
        e[u][v] = w;
    }

    dijkstra(s);

    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
        {
            cout<<dist[i];
        }
        else
        {
            cout<<" "<<dist[i];
        }
    }
    cout<<endl;

    return 0;
}