#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;
}