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


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



close(f2);

end.