#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, maxm = 5 * 1e5 + 5, INF = pow(2, 31) - 1;
struct edge
{
    int u, v;
    int w;
    int next;
} edge[maxm];
int head[maxn], cnt;
inline void adde(int u, int v, int w)
{
    edge[++cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int N, M, S, vis[maxn];
int dis[maxn];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q1;
void dij(int num)
{
    for (int i = 1; i <= N; i++)
        dis[i] = INF;
    dis[num] = 0;
    q1.push(make_pair(num, 0));
    pair<int, int> tmp;
    while (!q1.empty())
    {
        tmp = q1.top();
        q1.pop();
        int u = tmp.first;
        if (vis[u])
            continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            if (!vis[v] && dis[v] > dis[u] + edge[i].w)
            {
                dis[v] = dis[u] + edge[i].w;
                q1.push(make_pair(v, dis[v]));
            }
        }
    }
}

int main()
{
    cin >> N >> M >> S;
    for (int i = 1; i <= M; i++)
    {
        int u, v;
        int w;
        cin >> u >> v >> w;
        adde(u, v, w);
    }
    dij(1);
    for (int i = 1; i <= N; i++)
    {
        printf("%d ", dis[i]);
    }
}