#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;
}
int n, m, s, tot, dis[N], vis[N], head[N];
struct node
{
    int to;
    int nxt;
    int dis;
}h[N * 2];
void add(int u, int v, int d)
{
    h[++ tot].to = v;
    h[tot].nxt = head[u];
    h[tot].dis = d;
    head[u] = tot;
}
struct cmp
{
    bool operator()(int a, int b)
    {
        return dis[a] > dis[b];
    }
};
priority_queue<int, vector<int>, cmp> q;
void Dijkstra(int x)
{
    for (int i = 1; i <= n; i ++) dis[i] = INF;
    q.push(x);
    dis[x] = 0;
    while (!q.empty())
    {
        int now = q.top(); q.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        for (int j = head[now]; j; j = h[j].nxt)
        {
            int to = h[j].to;
            if (vis[to]) continue;
            if (dis[to] > dis[now] + h[j].dis)
            {
                dis[to] = dis[now] + h[j].dis;
                q.push(to);
            }
        }
    }
}
int main()
{
    n = read(), m = read(), s = read();
    for (int i = 1; i <= m; i ++)
    {
        int u = read(), v = read(), d = read();
        add(u, v, d);
    }
    Dijkstra(s);
    for (int i = 1; i <= n; i ++) printf("%d ", dis[i]);
    printf("\n");
    return 0;
}