using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Deykstr
{
    public class Program
    {
        const int n = 5;
        const int P = 99999;
        static bool[] masCheck = new bool[6];
        static int[] masEnd = { P, P, P, P, P, P  };
        static int[,] masLenght = {
                                  { 0, 7, 9, P, P, 14 },
                                  { 7, 0, 10, 15, P, P },
                                  { 9, 10, 0, 11, P, 2 },
                                  { P, 15, 11, 0, 6, P },
                                  { P, P, P, 6, 0, 9},
                                  { 14, P, 2, P, 9, 0}
                                  };
        static void Main()
        {
            Console.WriteLine("введите начальную точку");
            int nach = Int32.Parse(Console.ReadLine())-1;
            Console.WriteLine("введите конечную точку");
            int conech = Int32.Parse(Console.ReadLine())-1;

            int w;
            for (int ii = 0; ii <= n; ii++)
                masCheck[ii] = false;
            masEnd[nach] = 0;

            for (int i = 1; i <= n; i++)
            {
                w = Find_Min();

                for (int j = 1; j <= n; j++)
                {
                    if (masCheck[j] == false)
                        Relax(w, j);
                }

                masCheck[w] = true;

            }

                Console.WriteLine(masEnd[conech]);
                Console.WriteLine(masstr[conech]);

        }

        public static void Relax(int i, int j)
        {
            if (masEnd[j] > masEnd[i] + masLenght[i, j])
            {
                masEnd[j] = masEnd[i] + masLenght[i, j];
            }
        }
        public static int Find_Min()
        {
            int w = 0, min = P / 2;
            for (int i = 1; i <= n; i++)
            {
                if ((masCheck[i] == false) && masEnd[i] < min)
                {
                    min = masEnd[i];
                    w = i;
                }

            }
            return w;

        }

    }

}