记录编号	32816	评测结果	AAAAAAAAAA
题目名称	运输公司	最终得分	100
用户昵称	Des.	是否通过	通过
代码语言	Pascal	运行时间	0.352 s
提交时间	2011-11-08 16:00:31	内存使用	0.29 MiB

program transz;
uses math;
var a,c:array[1..20,1..20]of longint;
    b:array[1..100,0..20]of boolean;
    ans:array[0..100]of longint;
    ap:array[1..100,1..100]of longint;
    bo:array[1..20]of boolean;
    t,k,m,n,i,j,z,p,d,x,y:longint;
begin
assign(input,'transz.in');
reset(input);
assign(output,'transz.out');
rewrite(output);
readln(n,m,z,p);
for t:=1 to p do
  begin
    readln(i,j,k);
    a[i,j]:=k;
    a[j,i]:=k;
  end;
readln(p);
fillchar(b,sizeof(b),true);
for t:=1 to p do
  begin
    readln(k,i,j);
    for d:=i to j do
      b[d,k]:=false;
  end;
for x:=1 to n do
  for y:=x to n do
    begin
      fillchar(bo,sizeof(bo),true);
      for i:=1 to m do
        for j:=1 to m do
          c[i,j]:=a[i,j];
      for i:=x to y do
        for j:=1 to m do
          if b[i,j]=false then bo[j]:=false;
      for k:=1 to m do
        if bo[k] then
          for i:=1 to m do
            if bo[i] then
              for j:=1 to m do
                if bo[j] then
                  if (i<>k)and(k<>j)and(i<>j)and(c[i,k]>0)and(c[k,j]>0)
                  and(((c[i,k]+c[k,j])<c[i,j])or(c[i,j]=0)) then
                    c[i,j]:=c[i,k]+c[k,j];
      ap[x,y]:=c[1,m];
   end;
for i:=1 to n do ans[i]:=maxlongint;
ans[0]:=-z;
for i:=1 to n do
  for j:=0 to i-1 do
    if ap[j+1,i]>0 then
      ans[i]:=min(ans[i],ans[j]+ap[j+1,i]*(i-j)+z);
writeln(ans[n]);
close(output);
end.