const
       FIN = 'amenzi.in';
       FOUT = 'amenzi.out';
       NMAX = 151;
       TMAX = 3502;

  type
      time_matrix = array[ 0..NMAX, 0..TMAX ] of longint;
      graph = array[ 0..NMAX, 0..NMAX ] of longint;

  var
     S, T : time_matrix;
     A, COST : graph;
     f, g : text;
     N, M, K, P : longint;

 procedure read_data;
  var i, x, y, c : longint;
  begin
   assign( f, FIN ); reset( f ) ; readln( f, N, M, K, P );
   for i := 1 to M do
     begin
       readln( f, x, y, c );
       inc( A[x,0] ); A[ x, A[x,0] ] := y; COST[ x, y ] := c;
       inc( A[y,0] ); A[ y, A[y,0] ] := x; COST[ y, x ] := c;
     end;
   for i := 1 to K do
     begin
      readln( f, x, y, c );
      inc( S[ x, y ], c );
     end;
 end;

 function max( a, b : longint ) : longint;
  begin
   if a > b then max := a else max := b;
  end;

 procedure dinamica;
  var i, j, k, nod : longint;
  begin
    for i := 1 to N do T[ i, 0 ] := -1;
    T[ 1, 0 ] := S[ 1, 0 ];
    for i := 1 to TMAX do
     for j := 1 to N do
        begin
          T[ j, i ] := -1;
          if T[ j, i - 1 ] <> - 1 then T[ j, i ] := T[ j, i - 1 ] + S[ j, i ];
          for  k := 1 to A[j][0] do
             begin
               nod := A[j][k];
               if ( i - cost[ j, nod ] > -1 ) then
               if ( cost[ j, nod ] > 0 ) and ( T[ nod, i - cost[j,nod] ] <> - 1 ) then
               T[ j, i ] := MAX( T[ j, i ], T[ nod, i - cost[ j, nod ] ] + S[ j, i ] );
              end;
         end;
 end;

 procedure save;
  var i, x, y : longint;
  begin
   assign( g, FOUT ); rewrite( g );
   for i := 1 to P do
    begin
     readln( f, x, y );
     writeln( g, T[x,y] );
    end;
   close( f );
   close( g );
  end;

   begin
    read_data;
    dinamica;
    save;
   end.