#include <bits/stdc++.h>

using namespace std;
const int r = 1e2;
const int INF = 0x3f3f3f3f;

int main() {
    int N, M, start;
    cin >> N >> M >> start; // 输入起点

    int dist[r][r];
    memset(dist,INF,sizeof dist);

    for (int i = 0; i < M; ++i) {
        dist[i][i] = 0;
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }

    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for (int i = 1; i <= N; ++i) {
        if(dist[start][i]==INF) cout<<"-1 ";
        else cout << dist[start][i] << " ";
    }
    cout << endl;

    return 0;
}