#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Edge {
    int v, w;
    bool operator<(const Edge& e) const {
        return w > e.w;  // Obrnemo, ker je priority_queue max heap
    }
};

// https://putka-upm.acm.si/tasks/t/wolowitz/
int main() {
    int n, m, z, a, b, c;
    cin >> n >> m >> z;

    vector<vector<pair<int, int>>> G(n);
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> c;  // a -> b, cena c
        G[b].push_back({a, c});  // povezavo obrnemo zaradi besedila naloge
    }

    vector<int> dist(n, -1);
    // vector<int> prev(n, -1);
    priority_queue<Edge> q;
    q.push({z, 0});
    while (!q.empty()) {
        auto [c, d /*, p */] = q.top();  // current, distance
        q.pop();

        if (dist[c] != -1) continue;
        dist[c] = d;
        // prev[c] = p;

        // if (c == target) break;

        for (auto [u, w] : G[c]) {
            if (dist[u] == -1) {
                q.push({u, w+d, /* c */});
            }
        }
    }

    for (int d : dist) {
        cout << d << endl;
    }

    return 0;
}