#include <iostream>
#include <queue>
using namespace std;

const int maxn = 1e6 + 10;
long long e, Begin[maxn], To[maxn * 2], W[maxn * 2], Next[maxn * 2];
void add(long long u, long long v, long long w) {
    e++;
    To[e] = v;
    W[e] = w;
    Next[e] = Begin[u];
    Begin[u] = e;
}

long long n, m, dis[maxn];
bool vis[maxn];

struct node{
    long long id, value;
};

bool operator < (node A, node B) {
    if (A.value > B.value) return true;
    return false;
}

priority_queue <node> Q;
int main() {
    long long n, m, s; cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        long long u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        //add(v, u, w);
    }

    //初始化边界
    for (int i = 1; i <= n; i++)
        dis[i] = 1e20;
    dis[s] = 0;
    Q.push({s, 0});
    //算法过程
    while(!Q.empty()) {
        node temp = Q.top(); Q.pop();
        long long min_id = temp.id;
        long long val = temp.value;
        if (vis[min_id]) continue;
        vis[min_id] = 1;
        dis[min_id] = val;
        for (long long j = Begin[min_id]; j; j = Next[j]) {
            long long y = To[j], z = W[j];
            if (dis[y] > dis[min_id] + z) {
                dis[y] = dis[min_id] + z;
                Q.push({ y, dis[y] });
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << (long long)dis[i] << " ";
    return 0;
}