Program ThuatToanFloyd;
{ Tim duong di dai nhat tren do thi co huong, khong co chu trinh, moi dinh xuat hien dung mot lan tren duong di }
const fi = 'FLOYD.INP';
      fo = 'FLOYD.OUT';
      MAXN = 100;
      VoCung = MAXINT div 2;
var a: array [1..MAXN, 1..MAXN] of integer;
    n, s, t: integer;
    Truoc: array [1..MAXN, 1..MAXN] of integer;
    f: text;

    procedure Nhap;
    var i, j: integer;
    begin
        assign(f, fi); reset(f);
        readln(f, n, s, t);
        for i:= 1 to n do
                for j:= 1 to n do
                begin
                        read(f, a[i, j]);
                        a[i, j]:= -a[i, j];
                        Truoc[i, j]:= i;
                        if (a[i, j] = 0) and (i <> j) then
                                a[i, j]:= +VoCung;
                end;
        close(f);
    end;

    procedure Floyd;
    var k, u, v: integer;
    begin
        for k:= 1 to n do
                for u:= 1 to n do
                        for v:= 1 to n do
                                  if a[u, v] > a[u, k] + a[k, v] then
                                  begin
                                        a[u, v]:= a[u, k] + a[k, v];
                                        Truoc[u, v]:= Truoc[k, v];
                                  end;
    end;

    procedure TruyVet(u, v: integer);
    var k: integer;
    begin
        k:= Truoc[u, v];
        if k = u then
                write(f, ' -> ', v)
                else
                begin
                        TruyVet(u, k);
                        TruyVet(k, v);
                end;
    end;

    procedure KetQua;
    begin
        assign(f, fo); rewrite(f);
        writeln(f, -a[s, t]);
        write(f, s);
        TruyVet(s, t);
        close(f);
    end;

BEGIN
        Nhap;
        Floyd;
        KetQua;
END.