#include <bits/stdc++.h>  
  
using namespace std;  
  
const long long MAXN = 1e9+10;  
const int INF = 99999999;  
  
int main() {  
    long long n, m, s;  
    cin >> n >> m >> s; 
  
    long long e[MAXN][MAXN], dis[MAXN];  
    bool book[MAXN];  
    memset(book, 0, sizeof(book));  
    for (int i = 0; i < n; ++i) {  
        for (int j = 0; j < n; ++j) {  
            e[i][j] = INF;
        }  
        dis[i] = INF; 
    }  
    dis[s - 1] = 0; 
  
    int u, v, w;  
    for (int i = 0; i < m; ++i) {  
        cin >> u >> v >> w; 
        e[u - 1][v - 1] = w;  
    }  
  
    for (int i = 0; i < n - 1; ++i) {  
        int _min = INF, u_min;  
        for (int j = 0; j < n; ++j) {  
            if (!book[j] && dis[j] < _min) {  
                _min = dis[j];  
                u_min = j;  
            }  
        }  
        u = u_min;  
        book[u] = true;  
        for (int v = 0; v < n; ++v) {  
            if (e[u][v] != INF) {  
                if (dis[v] > dis[u] + e[u][v]) {  
                    dis[v] = dis[u] + e[u][v];  
                }  
            }  
        }  
    }  
  
    for (int i = 0; i < n; ++i) {  
        cout << dis[i] << " "; 
    }  
    cout << endl;  
  
    return 0;  
}