program poisk_min;
{$APPTYPE CONSOLE}
var
min,st,fin,n,i,j,k:integer;
d: array[1.. 100,1..100] of word;
dist,from: array[1..100] of word;
s:set of byte;

f1,f2:text;


begin
assign(f1,'graph.dat');reset(f1);
assign(f2,'graph.sol');rewrite(f2);
readln(f1,n);
for i:=1 to n do
for j:=1 to n do
read(f1,d[i,j]);
close(f1);
st:=1;
fin:=n;
S := [1 ..n]; S := S - [st];	{Підготовка множини не відвіданих вершин.}
for i:= 1 to n do {Перенесення у масив dist інформації про відстань до вершин.}
begin	{видимих зі стартової вершини st}
if d[st,i] = 0 then dist[i] := 65535 {Якщо ребро відсутнє, то відстань безмежна,}
else dist[i] := d[st, i];      {інакше така, як у таблиці суміжності. }
from[i] := st	{Усі вершини графа видимі зі стартової вершинні}
end;
from[st] := 0; dist[st] := 0;        {Стартова вершина видима ні з якої вершини.}

while s <> [] do {Виконання алгоритму, поки не будуть переглянуті всі вершини графа}
begin	{Визначення початкового мінімального значенню}
min := 65535;	{відстані між вершинами }
for i := 1 to n do {Перегляд усіх поточних відстаней між розглянутими вершинами}
if (i in s) and (dist[i] < min) and (dist[i] > 0) then {Визначення вершини k з}
begin min := dist[i]; k := i end; {мінімальним поточним значенням відстані.}
for i := 1 to n do	{Перегляд усіх вершин графа}
if (d[k, i] > 0) and (dist[i] > dist[k] + d[k, i]) then {і визначення найкоротшого}
begin
dist[i] := dist[k] + d[k, i];	{поточного шляху між вершинами i та j.}
from[i]:= k      {Запам'ятовування номера вершини, через яку зроблено}
end;	{перерахунок відстані.}
s:=s - [k];	{Надання вершині k статусу "відвіданої".}
end;

i := fin; {Початок формування шляху з фінішної вершини}

while i <>st do {Пошук шляху відбувається доти.}
begin {доки не потрапимо у стартову вершинї}
write(f2, from[i], '  ');{Виведення поточного значення вершини}
i :=from[i]{Перехід до вершини, з якої потрапили в поточнУ-1}
end;
write (f2, fin, ' ');{Виведення номера фінішної вершини}
writeln (f2);
writeln (f2, dist[fin]);
close(f2);

end.