#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int minDistance(int dist[],int visited[],int n){
    int min = INT_MAX,min_index;
    for(int v=0;v<n;v++){
        if(visited[v] == 0&& dist[v] <=min){
            min = dist[v];
            min_index = v;
        }
    } 
    return min_index;
}
void dijkstra(int n,int **graph,int src){
    int *dist=(int*)malloc(n* sizeof(int));
    int *visited =(int *)malloc(n* sizeof(int));
     
     for(int i=0;i<n;i++){
         dist[i] = INT_MAX;
         visited[i]=0;
     }
     dist[src]=0;
     for(int count =0;count<n-1;count++){
         int u = minDistance(dist,visited,n);
         if(u==-1)
         br
         visited[u] =1;
         for(int v=0;v<n;v++){
          if(!visited[v] && graph[u][v]!=0&&
             dist[u]!=INT_MAX && dist[u]+graph[u][v]<dist[v]){
             dist[v]=dist[u]+graph[u][v];
             }
         }
     }
     for(int i=0;i<n;i++){
         if(dist[i] == INT_MAX){
             printf("0");
         }else{
             printf("%d",dist[i]);
         }
         if(i!=n-1){
             printf(" ");
         }
     }
     free(dist);
     free(visited);
}
int main(){
    int n;
    if(scanf("%d",&n)!=1){
        printf("Invalid input");
        return 0;
    }
    if(n<0){
        printf("Invalid input");
        return 0;
    }
    if(n==0){
        return 0;
    }
    int **graph =(int**)malloc(n *sizeof(int*));
    for(int i=0;i<n;i++){
        graph[i]=(int*)malloc(n*sizeof(int));
    }
    
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        if(scanf("%d",&graph[i][j])!=1){
            printf("Invalid input");
            
            for(int k=0;k<n;k++){
                free(graph[k]);
            }
            free(graph);
            return 0;
        }
        if(graph[i][j]<0){
            printf("Invalid input");
            for(int k=0;k<n;k++){
                free(graph[k]);
            }
            free(graph);
            return 0;
        }
    }
}
int s;
if(scanf("%d",&s)!=1){
    printf("Invalid input");
     
     for(int i=0;i<n;i++){
         free(graph[i]);
     }
     free(graph);
     return 0;
}
if(s<0||s>=n){
    printf("Invalid input");
    
    for(int i=0;i<n;i++){
        free(graph[i]);
    }
    free(graph);
    return 0;
}
dijkstra(n,graph,s);
    for(int i=0;i<n;i++){
      free(graph[i]);   
}
    free(graph);
    return 0;
}