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

namespace PI1
{
    class Program
    {


        static void Main(string[] args)
        {

            Random rand = new Random();

            bool[] arr1 = new bool[100]; //массив посещения вершин
            int[] arr2 = new int[100]; //массив минимального расстояния от начала до данной вершины

            int n = 1;
            int[,] a;
            n = Convert.ToInt32(Console.ReadLine());
            a = new int[n, n];


            for (short i = 0; i < n; i++)
                for (short j = 0; j < n; j++)
                    try
                    {
                        a[i, j] = rand.Next(0, 20);
                        Console.WriteLine("Добавлено ребро: (" + i.ToString() + "; " + j.ToString() + ") весом " + a[i, j] + "\r\n");
                    }
                    catch
                    {
                        a[i, j] = 0;

                    }

            for (int i = 0; i < n; i++)   //матрица смежности
            {
                for (int j = 0; j < n; j++)
                    Console.Write("{0,-10}   ", a[i, j]);
                Console.WriteLine();
            }



            for (int beg = 0; beg < n; beg++)
            {
                for (int i = 0; i < n; i++)
                {
                    arr1[i] = true;
                    arr2[i] = 999999999;
                }
                arr2[beg] = 0;
                bool gr = true;
                int tekgr = beg; // граф
                while (gr == true)
                {
                    int min = 999999999, ming = 0;
                    for (int i = 0; i < n; i++)
                        if ((arr1[i] == true) && (a[tekgr, i] != 0) && (a[tekgr, i] + arr2[tekgr] < arr2[i]))
                            arr2[i] = arr2[tekgr] + a[tekgr, i];
                    arr1[tekgr] = false;
                    for (int i = 0; i < n; i++)                 // поиск "ближайшего" к началу графа
                        if ((arr2[i] < min) && (arr1[i] == true))
                        {
                            min = arr2[i];
                            ming = i;
                        }
                    tekgr = ming;
                    gr = false;
                    for (int i = 0; i < n; i++) //проверка, остались ли непосещенные графы
                        if (arr1[i] == true)
                            gr = true;
                }
                for (int i = 0; i < n; i++)
                {
                    Console.WriteLine("Минимальное расстояние от {0} поселения до {1} поселения = " + arr2[i], beg + 1, i + 1);
                    //Console.WriteLine(arr2[i]);
                }
            }