#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 2147483
using namespace std;
void Dijkstra(vector<vector<int> > mise, int n, int s, vector<int> &dist);
int findmindist(vector<vector<int> > mise, int n, vector<int> dist, vector<int> collect);
int fun(int n, int mise[][n])
int main()
{
    int n, m, s;
    cin >> n >> m >> s;

    vector<vector<int> > mise(n + 1, vector<int>(n + 1, MAX));
    int l, r, len;
    for(int i = 0; i < m; i++)
    {
        cin >> l >> r >> len;
        if(l != r)
        {
            mise[l][r] = min(mise[l][r], len);
        }
    }

    vector<int> dist(n + 1, MAX);

    Dijkstra(mise, n, s, dist);

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

    return 0;
}

void Dijkstra(vector<vector<int> > mise, int n, int s, vector<int> &dist)
{
    vector<int> collect(n + 1, 0);
    for(int i = 1; i <= n; i++)
    {
        if(mise[s][i] != 0)
        {
            dist[i] = mise[s][i];
        }
    }

    dist[s] = 0;
    collect[s] = 1;

    while(1)
    {
        int temp = findmindist(mise, n, dist, collect);
        if(temp == -1)
        {
            break;
        }
        else
        {
            collect[temp] = 1;
            for(int i = 1; i <= n; i++)
            {
                if(mise[temp][i] != MAX && collect[i] == 0)
                {
                    if(dist[temp] + mise[temp][i] < dist[i])
                    {
                        dist[i] = dist[temp] + mise[temp][i];
                    }
                }
            }
        }
    }
}

int findmindist(vector<vector<int> > mise, int n, vector<int> dist, vector<int> collect)
{
    int mini = MAX;
    int result;
    for(int i = 1; i <= n; i++)
    {
        if(collect[i] == 0 && dist[i] < mini)
        {
            mini = dist[i];
            result = i;
        }
    }

    if(mini == MAX)
    {
        return -1;
    }
    else
    {
        return result;
    }
}