program Gpaths;
type ADT=array[1..100000,1..3] of longint;
     AT=array[1..100000] of longint;
     ART=array[1..100000,1..2] of longint;
var im,jm,n,k,lt,c1,cr:longint;
    A,AD2:AT; AD:ADT; AR:ART;
    final,ep,yc:Boolean;
procedure Perm(var B:AT);
var i,p,t,j,c:longint;
    next:Boolean;
begin
 next:=true; c:=n;
 for i:=(n-2) downto 1 do if (B[i]>B[i+1]) and next then c:=c-1
 else next:=false;
 if c=1 then final:=true
 else if c=n then
 begin
  t:=B[n]; B[n]:=B[n-1]; B[n-1]:=t;
 end
 else
 begin
  p:=c;
  for i:=c-1 to n do if (B[i]>B[c-1]) and (B[i]<B[p]) then p:=i;
  begin
   t:=B[i]; B[i]:=B[p]; B[p]:=t;
  end;
  for i:=c to n-1 do
  for j:=i+1 to n do if B[j]<B[i] then
  begin
   t:=B[j]; B[j]:=B[i]; B[i]:=t;
  end;
 end;
end;
begin
 writeln('Za markirane krai na vuvejdane, vuvedete 0');
 readln(n,k);
 for im:=1 to n-1 do readln(AD[im,1],AD[im,2],AD[im,3]);
 for im:=1 to n do A[im]:=im;
 im:=1;
 final:=true;
 while final do
 begin
  readln(cr);
  if cr=0 then final:=false
  else
  begin
   AD2[cr]:=im; im:=im+1;
  end;
 end;
 for im:=1 to n do AR[im,1]:=1000000000;
 final:=false; yc:=false; ep:=true; lt:=1000000000; im:=1;
 while not final do
 begin
  Perm(A);
  while (im<>n-1) and ep and not yc do
  begin
   ep:=false;
   for jm:=1 to (n-1) do if ((AD[jm,1]=A[im]) and (AD[jm,2]=A[im+1])) or
                            ((AD[jm,2]=A[im]) and (AD[jm,1]=A[im+1])) then
   begin
    ep:=true;
    c1:=jm;
   end;
   if im<>1 then lt:=lt+AD[c1,3];
   if ((im<>1) and (AD2[im]<>0)) then
   begin
    yc:=true;
    cr:=AD2[im];
   end;
   if AR[A[1],1]>lt then
   begin
    AR[A[1],1]:=lt;
    AR[A[1],2]:=cr;
   end;
   im:=im+1;
  end;
 end;
 for im:=1 to n do writeln(AR[im,1],AR[im,2]);
end.
