/*
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
*/

#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 5;
struct Edge
{
    int next, to;
    int w;
} edge[(MAX_N << 1) + 5];

int head[MAX_N];
int cnt;

void init(int n)
{
    for (int i = 0; i <= n; i++)
    {
        head[i] = edge[i].next = -1;
    }
    cnt = 0;
}

void addedge(int u, int v, int w)
{
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

struct s_node
{
    int id;
    int dis;

    s_node(int a, int b)
    {
        id = a, dis = b;
    }

    bool operator<(const s_node &a) const
    {
        return dis < a.dis;
    }
};


int dis[MAX_N];
int done[MAX_N];

void dijkstra(int s)
{
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    memset(done, 0, sizeof(done));

    dis[s] = 0;
    priority_queue<s_node> q;
    q.push(s_node(s, dis[s]));
    while (!q.empty())
    {
        s_node now = q.top();
        q.pop();

        if (done[now.id])continue;
        done[now.id] = 1;
        for (int i = head[now.id]; ~i; i = edge[i].next)
        {
            Edge y = edge[i];

            if (dis[y.to] > dis[now.id] + y.w)
            {
                dis[y.to] = dis[now.id] + y.w;
              if (!done[y.to])
                q.push(s_node(y.to, dis[y.to]));
            }
        }
    }
}

int main()
{

    int n, m, s, u, v, w;

    scanf("%d %d %d", &n, &m, &s);

    init(n);
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        addedge(u, v, w);
    }
    dijkstra(s);

    for (int i = 1; i <= n; i++)
    {
        printf("%d ", dis[i]);
    }

    return 0;
}