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

const int lnf = INT_MAX/2;

struct Pair {
    int to, cost;
};

bool operator>(Pair a, Pair b){
	return a.cost < b.cost;
}

int main() {
    int n, m, start;
    scanf("%d%d%d", &n, &m, &start);
    start--;
    // Build Graph
    vector<vector<Pair>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        g[u].push_back({ v, w });
    }

    vector<int> dis(n, lnf);
    dis[start] = 0;

    priority_queue<Pair, vector<Pair>, greater<Pair>> q;
    q.push({ start, 0 });
    while (!q.empty()) {
        Pair p = q.top(); q.pop();
        int x = p.to, cost = p.cost;
        if (dis[x] < cost) continue;
        for (Pair &y : g[x]) {
            int di = dis[x] + y.cost;
            if (di < dis[y.to]) {
                dis[y.to] = di;
                q.push({ y.to, di });
            }
        }
    }

    for (auto &d : dis) {
        printf("%d ", d);
    }

    return 0;
}