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

#define endl '\n';
struct shortest_path {
    struct edge {
        int to;
        int l;
    };
    const int INF = 1e10;
    vector<int> dist;
    vector<bool> b;
    vector<vector<edge>> g;
    shortest_path(int n) :
                           dist(n + 1, INF), g(n), b(n, false) {}

    void dijkstra (int n, int m, int s) { 
        for (int i = 0; i < m; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            --u;
            --v;
            g[u].push_back({v, w});
        }
        dist[s] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ds;
        ds.emplace(0, s);
        while (!ds.empty()) {
            auto k = ds.top().second;
            ds.pop();
            if (b[k]) {
                continue;
            }
            for (auto i : g[k]) {
                if (dist[k] + i.l < dist[i.to] && dist[k] + i.l > 0) {
                    dist[i.to] = dist[k] + i.l;
                    ds.emplace(dist[i.to], i.to);
                }
            }
            b[k] = true;
        }
        for (int i = 0; i < n; ++i) {
            cout << dist[i] << " ";
        }
    }
};

void best_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    shortest_path sp(n);
    sp.dijkstra(n, m, s - 1);
}

int main() {
    best_coder();


    // 返回
    return 0;
}