#include <bits/stdc++.h>
using namespace std;

const int N = 100001, M = 500001;

int n, m, s, d[N], head[N], nxt[M], ecnt;
bool vis[N];

struct node {
    int v, w;
    friend bool operator<(const node &a, const node &b) { return a.w > b.w; }
} edge[M];

inline void add(int u, int v, int w) {
    nxt[++ecnt] = head[u];
    head[u] = ecnt;
    edge[ecnt] = (node){v, w};
}

priority_queue<node> q;

int main() {
    // freopen("E:/Desktop/P3371_2.in", "r", stdin);
    // freopen("E:/Desktop/P3371.out", "w", stdout);
    memset(d, 0x3f, sizeof(d));
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    d[s] = 0;
    q.push((node){s, 0});
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (vis[u.v]) continue;
        vis[u.v] = true;
        for (int i = head[u.v]; i; i = nxt[i]) {
            node v = edge[i];
            if (d[v.v] > d[u.v] + v.w) {
                d[v.v] = d[u.v] + v.w;
                q.push((node){v.v, d[v.v]});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << (d[i] != 0x3f ? d[i] : 2147483647) << " ";
    }
    return 0;
}