#include <stdio.h>
const int INF = 100000;
void dijkstra(int s, int n, int a[n][n], int **r) {
    int d[n];
    int visited[n];
    int index;
    int u;
    for (int i = 0; i < n; ++i) {
        d[i] = INF;
        visited[i] = 0;
    }
    d[s] = 0;
    for (int i = 0; i < n; ++i) {
        int v = INF;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && (d[j] <= v)) {
                v = d[j];
                index = j;
            }
        }
            u = index;
            visited[u] = 1;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && a[u][j] && d[u] != INF && (d[u] + a[u][j]) < d[j]) {
                    d[j] = d[u] + a[u][j];
                }
            }
    }
    for (int i = 0; i < n; ++i) {
        if (d[i] != INF) {
            r[i] = d[i];
        }
        else {
            r[i] = -1;
        }
    }
}

int main() {
    int n, m, s;
    FILE *fi = fopen("input.txt", "r");
    fscanf(fi, "%d%d%d", &n, &m, &s);
    printf("%d%d%d", n, m, s);
    int matrix[n][n];
    int a = 0, b = 0, c = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            matrix[i][j] = 0;
        }
    }
    while (fscanf(fi, "%d%d%d", &a, &b, &c) != EOF) {
        printf("\n%d%d%d", a, b, c);
        matrix[a-1][b-1] = c;
    }
    fclose(fi);
    printf("\n");
    int r[n];
    dijkstra(s-1, n, matrix, &r);
    for (int i = 0; i < n; i ++) {
        printf("%d ", r[i]);
    }

    return 0;
}