#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int n, m, k, s;
    cin >> n >> m >> k >> s;
    s--;
    vector<pair<pair<int,int>,long long>> vertex;
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long w;
        cin >> a >> b >> w;
        a--; b--;
        graph[a].push_back(b);
        pair<int,int> p={a,b};
        pair<pair<int,int>,long long> elem = {p,w};
        vertex.emplace_back(elem);
    }
    vector<vector<long long>> d(k + 1,vector<long long> (n, LONG_LONG_MAX));
    d[0][s] = 0;
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < m; ++j) {
            if (d[i - 1][vertex[j].first.first] < LONG_LONG_MAX) {
                d[i][vertex[j].first.second] = min(d[i][vertex[j].first.second],
                                                   d[i - 1][vertex[j].first.first] + vertex[j].second);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (d[k][i] >= LONG_LONG_MAX) {
            cout << -1 << endl;
        }
        else {
            cout << d[k][i] << endl;
        }
    }
}