#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
const int infinity = 10000;
class dijkstra
{
      private:
              int graph[512][512];// build an empty matrix 
              int set[512],predecessor[512],mark[512],pathestimate[512];
              int source;
              int verticesNum;
      public:
             int minimum();
             void read();
             void initialize();
             void printpath(int);
             void algorithm();
             void output();
};
void dijkstra::read()
{
     string filename;
     ifstream infile;
     cout<<"Please input a file name:";
     cin>>filename;
     infile.open(filename.c_str());
     if (infile.fail()){
                        cout<<" invalid file!"<<endl;
     }
     else 
     {
         infile >> verticesNum;//get the num of vertices 
         //build an adjacent matrix
         for(int i=1;i<=verticesNum;i++)
         {
                 for(int j=1;j<=verticesNum;j++)
                 {
                         infile >> graph[i][j];
                 }
         }
         //select the source vertex;
         infile>>source;
         infile.close();        
     }
}

void dijkstra::initialize()
{
    for(int i=1;i<=verticesNum;i++)
    {
      mark[i] = 0;
      pathestimate[i] = infinity;
      predecessor[i] = 0;
    }
    pathestimate[source] = 0;
}
void dijkstra::algorithm()
{
    initialize();
    int count = 1;
    int i;
    int j;
    while(count <= verticesNum)
    {
        j = minimum();
        set[++count] = j;
        mark[j] = 1;
        for(i=1;i<=verticesNum;i++)
        {
          if(graph[j][i]>0)
          {
              if(mark[i]!= 1)
              {
                        if(pathestimate[i]>pathestimate[j]+graph[j][i])
                        {
                              pathestimate[i] = pathestimate[j]+graph[j][i];
                              predecessor[i] = j;
                        }
              }
          }
        }
    }
}

void dijkstra::printpath(int i)
{
     if(i != source)
     {
          if(predecessor[i]==0){
                    cout<<"-1"<<" ";
          }
          else
          {
              printpath(predecessor[i]);
          }
     }
}

void dijkstra::output()
{

     for(int i=1;i<=verticesNum;i++)
     {
             printpath(i);
             if(pathestimate[i]!= infinity)
             cout<<pathestimate[i]<<" ";
     }
     cout<<endl;
}
int dijkstra::minimum()
{
  int min = infinity;
  int i,t;
  for(i=1;i<=verticesNum;i++)
  {
    if(mark[i]!=1)
    {
      if(min>=pathestimate[i])
      {
                min=pathestimate[i];
                t=i;
      }
    }
      
  }
  return t;
}
int main()
{
    dijkstra s;
    s.read();
    s.algorithm();
    s.output();
    system ("pause");
    return 0;
}