const int maxn = 1e4 + 10;
const int N = 1e5 + 10;
const int inf = 1e9;
int n, m, s;
int dis[maxn];
int vis[maxn];
int w[maxn][maxn];

void dij(int s) {
    mm(vis, 0);
    mm(dis, 0x3f);
    dis[s] = 0;
    for (int i = 1; i <= n; i++) {
        int num = 0;
        int minn = 0x3f3f3f3f;
        for (int j = 1; j <= n; j++) {
            if (vis[j] == 0 && dis[j] < minn) {
                minn = dis[j];
                num = i;
            }
        }
        if (num == 0) break;
        vis[num] = 1;
        for (int j = 1; j <= n; j++) {
            if (vis[j] == 0 && dis[j] > dis[num] + w[num][j])
                dis[j] = dis[num] + w[num][j];
        }
    }
}

signed main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            w[i][j] = 0x3f3f3f3f;
        }
    }
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (w[a][b] > c)
            w[a][b] = c;
    }
    dij(s);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    cout << endl;
}