#3wa求调

#include <bits/stdc++.h>
using namespace std;
bool vis[114514];
const long long INF = 0x3f3f3f3f;
long long cnt;

struct edge
{
    int v;
    int w;
    int next;
} edge[1145141];
int head[114514];

void addedge(int a, int b, int c)
{
    cnt++;
    edge[cnt].v = b;
    edge[cnt].w = c;
    edge[cnt].next = head[a];
    head[a] = cnt;
}
int main()
{
    long long minn;
    long long dis[114514];
    int n, m, s;
    int a, b, c;
    cin >> n >> m >> s;

    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        addedge(a, b, c);
    }
    int cur = s;
    dis[s] = 0;
    while (!vis[cur])
    {
        vis[cur] = true;
        for (int i = head[cur]; i != 0; i = edge[i].next)
        {
            if (!vis[edge[i].v] && dis[edge[i].v] > dis[cur] + edge[i].w)
                dis[edge[i].v] = dis[cur] + edge[i].w;
        }
        long long minn = INF;
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && minn > dis[i])
            {
                minn = dis[i];
                cur = i;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    return 0;
}