const
  oo=maxlongint div 2;

var
  n,i,x,j,y,z,p,m:longint;
  a,g:array[0..1000,0..1000]of longint;
  v:array[0..10000]of boolean;
  q,d:array[0..10000]of longint;

procedure spfa;
var
  h,x,t,i:longint;
begin
  h:=1;
  t:=1;
  for i:=1 to n do
  begin
    v[i]:=false;
    d[i]:=oo;
    q[i]:=0;
  end;
  v[1]:=true;
  q[1]:=1;
  d[1]:=0;
  repeat
    x:=q[h];
    for i:=1 to n do
    if d[x]+g[x,i]<d[i] then
    begin
      d[i]:=d[x]+g[x,i];
      if not v[i] then
      begin
        v[i]:=true;
        inc(t);
        q[t]:=i;
      end;
    end;
    v[x]:=false;
    inc(h);
  until h>t;
end;

begin
  assign(input,'rebuild.in'); reset(input);
  assign(output,'rebuild.out'); rewrite(output);
  readln(n);
  readln(m);
  for i:=1 to n do
   for j:=1 to n do
   g[i,j]:=oo;

  for i:=1 to m do
  begin
    readln(x,y,z);
    g[x,y]:=0;
    g[y,x]:=0;
    a[x,y]:=z;
    a[y,x]:=z;
  end;

  readln(p);
  for i:=1 to p do
  begin
    readln(x,y);
    g[x,y]:=a[x,y];
    g[y,x]:=a[y,x];
  end;
  spfa;
  writeln(d[n]);
  close(input);
  close(output);
end.