#include <bits/stdc++.h>

using namespace std;

int n, m, s;

struct Edge {
    int u, v, w;
};

vector<Edge> adj[10010];
int dis[10010];
int vis[10010];

void SPFA(int s) {
    for (int i = 1; i <= n; ++i) {
        dis[i] = INT_MAX;
        vis[i] = 0;
    }

    queue<int> pq;
    pq.push(s);
    dis[s] = 0;
    vis[s] = 1;

    while (!pq.empty()) {
        int t = pq.front();
        pq.pop();
        vis[t] = 0;

        for(int i = 0;i < adj[t].size(); ++i){
            Edge e = adj[t][i];
            if (dis[e.v] > dis[e.u] + e.w) {
                dis[e.v] = dis[e.u] + e.w;
                if(!vis[e.v]){
                    pq.push(e.v);
                    vis[e.v] = 1;
                }
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m >> s;

    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({u, v, w});
    }
    SPFA(s);

    for (int i = 1; i <= n; ++i) {
        cout << dis[i] << " ";
    }

    return 0;
}