ZZXYY's blog

var
  a,dis:array[0..200]of longint;
  v,w,next,que:array[1..10000]of longint;
  f:array[0..1000]of longint;
  b:array[0..200,0..1000]of boolean;
  inq,eb:array[0..200]of boolean;
  c:array[0..100,0..100]of longint;
  n,m,i,j,k,l,t,p,q,r,e,head,tail,kk:longint;
procedure adde(uu,vv:longint);
begin
  inc(k);
  v[k]:=vv;
  w[k]:=r;
  next[k]:=a[uu];
  a[uu]:=k;
  inc(k);
  v[k]:=uu;
  w[k]:=r;
  next[k]:=a[vv];
  a[vv]:=k;
end;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
procedure spfa;
var
  i:longint;
begin
  tail:=1;
  head:=0;
  fillchar(dis,sizeof(dis),255);
  fillchar(inq,sizeof(inq),false);
  dis[1]:=0;
  inq[1]:=true;
  que[1]:=1;
  repeat
    inc(head);
    if head>1000 then head:=1;
    p:=que[head];
    i:=a[p];
    while i<>0 do
    begin
      q:=v[i];
      if eb[q] then
      begin
        if (dis[q]=-1) or (dis[p]+w[i]<dis[q]) then
        begin
          dis[q]:=dis[p]+w[i];
          if not inq[q] then
          begin
            inq[q]:=true;
            inc(tail);
            if tail>1000 then tail:=1;
            que[tail]:=q;
          end;
        end;
      end;
      i:=next[i];
    end;
    inq[p]:=false;
  until head=tail;
end;
begin
  read(n,m,kk,e);
  for i:=1 to e do
  begin
    read(p,q,r);
    adde(p,q);
  end;
  read(k);
  fillchar(b,sizeof(b),true);
  fillchar(f,sizeof(f),100);
  for i:=1 to k do
  begin
    read(r,p,q);
    for j:=p to q do
    b[r,j]:=false;
  end;
  for i:=1 to n do
  for j:=i to n do
  begin
    fillchar(eb,sizeof(eb),true);
    for k:=1 to m do
    for l:=i to j do
    if not b[k,l] then
    begin
      eb[k]:=false;
      break;
    end;
    spfa;
    c[i,j]:=dis[m]*(j-i+1);
    if dis[m]=-1 then c[i,j]:=214748364;
  end;
  f[0]:=-kk;
  for i:=1 to n do
  for j:=0 to i-1 do
  f[i]:=min(f[i],f[j]+c[j+1,i]+kk);
  writeln(f[n]);
end.