#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
int minDistance(long long dist[], bool sptSet[], int n) {
    long long min = INF;
    int min_index = -1;
    for (int v = 0; v < n; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}
void dijkstra(int n, int graph[n][n], int s) {
    long long dist[n];
    bool sptSet[n];
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        sptSet[i] = false;
    }
    dist[s] = 0;
    for (int count = 0; count < n - 1; count++) {
        int u = minDistance(dist, sptSet, n);
        if (u == -1) break;
        sptSet[u] = true;
        for (int v = 0; v < n; v++) {
            if (!sptSet[v] && graph[u][v] != 0 && dist[u] != INF && (dist[u] + graph[u][v] < dist[v])) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF)
            printf("-1");
        else
            printf("%lid", dist[i]);
        if (i < n - 1) printf(" ");
    }
    printf("\n");
}
int main() {
    int n, s;
    if (scanf("%d", &n) != 1) {
        return 1;
    }
    if (n < 0 || n > 100) {
        printf("Invalid input\n");
        return 0;
    }
    if (n == 0) {
        return 0;
    }
    int matrix[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (scanf("%d", &matrix[i][j]) != 1) {
                return 1;
            }
            if (matrix[i][j] < 0) {
                printf("Invalid input\n");
                return 0;
            }
        }
    }
    if (scanf("%d", &s) != 1) {
        return 0;
    }
    if (s < 0 || s >= n) {
        printf("Invalid input\n");
        return 0;
    }
    dijkstra(n, matrix, s);
    return 0;
}