#include<stdio.h>
#include<limits.h>
#define MAX 100
#define INF INT_MAX
int main(){
    int n;
    
    if(scanf("%d", &n) !=1 || n<= 0 || n>MAX){
        printf("Invalid input");
        return 0;
    }

    int graph [MAX][MAX];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(scanf("%d",&graph[i][j])!=1 || graph[i][j]>1000000){
                printf("Invalid input");
                return 0;
            }
        
    
    int src;
    if(scanf("%d",&src)!=1 || src < 0 || src >=n){
         printf("Invalid input");
        return 0;
    }

    int dist[MAX];
    for(int i=0;i<n;i++) dist[i]= INF;
    dist[src] = 0;
        


int has_negative = 0;
for(int i=0;i<n;i++)
    for(int j=0; j<n;j++)
        if(graph[i][j]< 0 ) has_negative=1;
        
if(has_negative){
        for(int k=0;k<n-1;k++){
             for(int i=0; i<n;i++){
                 if(dist[i] == INF)
                 continue;
                 for(int j=0; j<n;j++){
                      if(graph[i][j]!=0 && dist[i]!= INF && dist[i]+ graph[i][j]<dist[j]){
                         dist[j]= dist[i]+ graph[i][j];            
                      }
                 }
             }
        }   
    int neg_cycle=0;
    for(int u=0; u<n;u++){
        if(dist[u]==INF) continue;
        for(int v=0;v<n;v++){
            if(graph[u][v]!= 0 && dist[u]+ graph[u][v] < dist[v]){
                neg_cycle = 1;
                break;
        }
    }
}
if(neg_cycle){
    printf("Invalid input");
    return 0;
}
else{
int visited[MAX]= {0};
for(int count=0; count<n-1; count++){
    int u =-1;
    int mindist = INF;
    for(int i=0;i<n;i++){
        if(!visited[i] && dist[i] < mindist){
            mindist = dist[i];
            u = i;
        }
    }
    if(u == -1) break;
    visited[u]= 1;
        for(int v=0;v<n;v++){
            if(!visited[v] && graph[u][v] && 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("INF");
        else
        printf("%d",dist[i]);
        
        if(i<n-1) printf(" ");
    }
    printf("\n");
    return 0;
}