uses crt;
type mas=array [1..100] of integer;
type rec=record
       zala:integer;
       put:integer;
     end;
     mas1=array [1..100] of rec;
     mas2=array [1..100] of mas1;
var f,t:text;
    n,i,j,p,h:integer;
    c,k:mas;
    a:mas2;
Procedure WriteMas(var c:mas;var f:text);
var z,x,y,o,m:integer;
begin
  reset(f);
  readln(f);
  x:=-1;
  for z:=1 to n-1 do begin
                       if (z mod 2 = 1) then begin
                                               x:=x+2;
                                               y:=x;
                                             end;
                       y:=y+1;
                       readln(f,o,m,c[z]);
                       if not ((o=x) and (m=y) and (c[z]>=1) and (c[z]<=100000)) then begin
                                                            writeln('Greshka');
                                                            readln;
                                                            exit;
                                                                                     end;
                    end;
  close(f);
end;
Procedure Shortcut(var f:text;var a:mas2);
var q:mas;
    r,e,u,v,m,l,g,y,z,x:integer;
begin
  reset(f);
  for r:=1 to n do readln(f);
  for r:=1 to p do readln(f,q[r]);
  for r:=1 to n do for v:=1 to n do
                     begin
                       reset(f);
                       readln(f);
                       repeat
                         readln(f,e,u,x);
                       until (e=r) or (u=r);
                       for m:=1 to p do if u=q[m] then begin
                                        a[r][v].put:=x;
                                        a[r][v].zala:=e;
                                        break;
                                      end
                                 else if (r<>q[m]) then begin
                                    l:=0;
                                    repeat
                                    l:=l+1;
                                    readln(f,g,z,y);
                                    if (g=e) or (z=e) then begin
                                    a[r][v].put:=a[r][v].put+y;
                                    if e=g then e:=z else e:=g;
                                    a[r][v].zala:=z;
                                                          end;
                                  until (l=n-r) or (z=r)
                                  end;
                                  end;
                                  end;
Procedure Sort(var a:mas2);
var i,j,x:integer;
    b:rec;
begin
for x:=1 to n do
for i:=1 to p-1 do for j:=i+1 to p do if a[x][i].put>a[x][j].put then
begin
  b:=a[x][i];
  a[x][i]:=a[x][j];
  a[x][j]:=b;
end;
end;
Procedure WriteT(var t:text;var a:mas2);
var i:integer;
begin
  rewrite(t);
  for i:=1 to n do writeln(t,a[i][1].zala,' ',a[i][1].put);
  close(t);
end;
BEGIN
  clrscr;
  assign(f,'C:\B_48\GPATHS.in');
  assign(t,'C:\B_48\GPATHS.out');
  reset(f);
  readln(f,n,p);
  if not ((n>=3) and (n<=100) and (p>=2) and (p<=n)) then begin
                                                            writeln('Greshka');
                                                            readln;
                                                            exit;
                                                          end;
  reset(f);
  for i:=1 to n do readln(f);
  for i:=1 to p do readln(f,k[p]);
  WriteMas(c,f);
  Shortcut(f,a);
  Sort(a);
  WriteT(t,a);
  readln;
end.