using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;


namespace Dijkstry
{
    class Program
    {

        static void Djk(int[][] tablica, int startowy, int wierzcholki)
        {
            StreamWriter sw = new StreamWriter("Out0304.txt");
            int[][] D = new int[wierzcholki - 1][];
            int min = 100, i = 0, pom = 0, pom2 = 1;
            int poprzednik_nr = 0;
            int[] Dist = new int[wierzcholki];
            int[] Pred = new int[wierzcholki];
            Pred[startowy-1] = -1;
            for (i = 0; i < wierzcholki; i++)   //uzupelnienie dystansu -1
                Dist[i] = -1;
            Dist[startowy - 1] = 0;       //dla startowego zawsze 0
            for (i = 0; i < wierzcholki - 1; i++)
                D[i] = new int[wierzcholki];
            for (int j = 0; j < wierzcholki - 1; j++)
            {
                min = 100;
                for (int k = 0; k < wierzcholki; k++)
                {
                    if (j == 0)
                    {
                        D[j][k] = tablica[startowy - 1][k];     //pierwsza linia przepisanie dla startu
                        if (min > tablica[startowy - 1][k])     //wyszukanie minimum
                        {
                            min = tablica[startowy - 1][k];
                            poprzednik_nr = k;              //nr dla minimum
                        }

                    }
                    else
                    {
                        if (Dist[k] == -1)  // jezeli wierzcholek jeszcze nie wystapil to zadziala
                        {
                            if (D[j - 1][k] <= tablica[pom2][k] + pom)       //uzupelnienie dikstry
                            {
                                D[j][k] = D[j - 1][k];
                                if (min > D[j][k])
                                {
                                    min = D[j][k];
                                    poprzednik_nr = k;

                                }
                            }
                            else
                            {
                                D[j][k] = tablica[pom2][k] + pom;
                                if (min > D[j][k])
                                {
                                    min = D[j][k];
                                    poprzednik_nr = k;
                                }
                            }
                        }
                    }
                }
                if (j == 0){
                    Pred[poprzednik_nr] = startowy;
                    pom = min;
                    pom2 = poprzednik_nr;
                    Dist[poprzednik_nr] = min;
                }
                else {


                    if (min != tablica[pom2][poprzednik_nr] + pom)      // jezeli wartosc sie nie zmienia predykat tez nie
                        Pred[poprzednik_nr] = Pred[pom2];
                    else Pred[poprzednik_nr] = pom2 + 1;

                    pom = min;
                    pom2 = poprzednik_nr;
                    Dist[poprzednik_nr] = min;
                }
                }

            for (i = 0; i < wierzcholki; i++)
                sw.Write(Dist[i] + " ");
            sw.WriteLine();
            for (i = 0; i < wierzcholki; i++)
                sw.Write(Pred[i] + " ");

            sw.Close();
        }
        static void Main(string[] args)
        {
            int[][] tablica = null;
            StreamReader sr = new StreamReader("In0304.txt");
            int wierzcholki = 0, startowy = 0; ;
            int i = 0, j = 0;
            string w = null;
            string[] pom = null;
            while (!sr.EndOfStream)
            {
                w = sr.ReadLine();
                pom = w.Split(' ');
                if (pom.Length == 2)
                {
                    wierzcholki = Int32.Parse(pom[0]); startowy = Int32.Parse(pom[1]);
                    tablica = new int[wierzcholki][];
                    for (i = 0; i < wierzcholki; i++)
                        tablica[i] = new int[wierzcholki];
                    i = 0;
                }
                else
                {
                    j = 0;
                    while (j < pom.Length)
                    {

                        tablica[i][j] = Int32.Parse(pom[j]);
                        j++;
                    }

                    i++;
                }
            }
            Djk(tablica, startowy, wierzcholki);
            Console.ReadLine();
            sr.Close();
        }
    }
}