import java.util.*;

class Main{
    static final int INF = Integer.MAX_VALUE;
   
    
    int minDistance(int[] dist,Boolean[] sptSet,int V){
        int min= INF ,min_index = -1;
        
        for(int v=0;v<V;v++){
            if(!sptSet[v] && dist[v] <= min){
                min = dist[v];
                min_index = v;
            }
        }
        return min_index;
    }
    
    void dijkistra(int[][] graph,int src,int V){
        int dist[] = new int[V];
        Boolean[] sptSet = new Boolean[V];
        
        Arrays.fill(dist,INF);
        Arrays.fill(sptSet,false);
        
        dist[src] = 0;
        
        for(int cnt=0;cnt<V-1;cnt++){
            int u= minDistance(dist,sptSet,V);
            sptSet[u] = true;
            for(int v=0;v<V;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];
                }
            }
        }
        printSolution(dist,V);
    }
    void printSolution(int[] dist,int V){
        System.out.println("Vertex \t Distance fromSource");
        for(int i=0;i<V;i++){
            System.out.println(i+"\t"+dist[i]);
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        System.out.println("Enter the number of vertices:");
        int n =sc.nextInt();
        
        System.out.println("Enter the adjacancy matrix");
        int[][] graph = new int[n][n];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                graph[i][j] = sc.nextInt();
            }
        }
        
        System.out.println("Enter the source:");
        int src=sc.nextInt();
        Main obj = new Main();
        obj.dijkistra(graph,src,n);
    }
}