#include<stdio.h>
#include<iostream>
//#include<conio.h>
#define N 3
using namespace std;
/* 
   if you wish to change the number of nodes just change the value 
   "N" given above.
*/

int min(int distance[N],int visited[N])
{
    
    int min=1000,pos,flag=0;
    for(int i=0;i<N;i++)
    {
            if((distance[i] != 0)&&(visited[i] != i))
            {
               if(distance[i]<min)
               {
                 min=distance[i];
                 pos =i;
               }
            }
   }
   return pos;
}

void dijkstra(int graph[N][N],int source)
{
   
   int i,j=1,distance[N],current,visited[N],k=0;
   for(i=0;i<N;i++)
   {
                   distance[i] = graph[source][i];
                   visited[i] = -1;
                   
   }
   distance[source]=0;
   visited[source]=source;
   
   
   while(j<N)
   {
       current = min(distance,visited);
      
       visited[current] = current;
       j++;
      
       
       for(int i=0;i<N;i++)
       {
               if(graph[current][i] != 0 && visited[i] != i)
               {
                                    if(distance[i] == 0)
                                    {
                                                  distance[i] = graph[current][i]+distance[current];
                                              
                                    } 
                                    else
                                    {                                                  
                                       if( distance[i] > graph[current][i]+distance[current])
                                       {
                                           distance[i] = graph[current][i]+distance[current];
                                          
                                       }
                                    }
               }
               
          
               
       }
   } 
   
  for(int i=0;i<N;i++)
           cout<<" "<<distance[i];
}      
        
             
             
                             
                          
                             
   
                     

int main()
{
    int graph[N][N],i,j,source;
    cout<<"enter the nodes of the graph\n";
    for(i=0;i<N;i++)
    {
                    for(j=0;j<N;j++)
                    {
                                   
                                   do
                                   {
                                     cin>>graph[i][j];
                                   }while(graph[i][j]<0);
                    }
  }
  
  cout<<"give the source node";
  cin>>source;
 
  dijkstra(graph,source);
 
 
 
// getch();
 return 0;
}