记录编号	26825	评测结果	AAAAAAAAA
题目名称	道路重建	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.001 s
提交时间	2011-07-27 17:38:25	内存使用	1.37 MiB

{道路重建 2011/07/27NOI模拟赛
 最短路径SPFA
 Author: yangbohua
 Time: 2011-07-27}
 
program rebuild;
const
  maxn=200;
  maxm=40000;
type
  node=record
    v,w,next:longint;
  end;
var
  list,dist,q:array[0..maxn] of longint;
  map:array[0..maxm] of node;
  edge,edge1:array[0..maxm,1..3] of longint;
  b,bb:array[0..maxn] of boolean;
  n,m,m1,i,j,u,ss,tt,h,t,e,y:longint;

procedure sort(l,r:longint);
var
  i,j,x1,x2,y:longint;
begin
  x1:=edge[(l+r) div 2,1];
  x2:=edge[(l+r) div 2,2];
  i:=l;
  j:=r;
  repeat
    while (edge[i,1]<x1) or ((edge[i,1]=x1) and (edge[i,2]<x2)) do inc(i);
    while (edge[j,1]>x1) or ((edge[j,1]=x1) and (edge[j,2]>x2)) do dec(j);
    if i<=j then
    begin
      y:=edge[i,1]; edge[i,1]:=edge[j,1]; edge[j,1]:=y;
      y:=edge[i,2]; edge[i,2]:=edge[j,2]; edge[j,2]:=y;
      y:=edge[i,3]; edge[i,3]:=edge[j,3]; edge[j,3]:=y;
      inc(i); dec(j);
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

procedure sort1(l,r:longint);
var
  i,j,x1,x2,y:longint;
begin
  x1:=edge1[(l+r) div 2,1];
  x2:=edge1[(l+r) div 2,2];
  i:=l;
  j:=r;
  repeat
    while (edge1[i,1]<x1) or ((edge1[i,1]=x1) and (edge1[i,2]<x2)) do inc(i);
    while (edge1[j,1]>x1) or ((edge1[j,1]=x1) and (edge1[j,2]>x2)) do dec(j);
    if i<=j then
    begin
      y:=edge1[i,1]; edge1[i,1]:=edge1[j,1]; edge1[j,1]:=y;
      y:=edge1[i,2]; edge1[i,2]:=edge1[j,2]; edge1[j,2]:=y;
      inc(i); dec(j);
    end;
  until i>j;
  if l<j then sort1(l,j);
  if i<r then sort1(i,r);
end;

procedure addedge(i,j,w:longint);
begin
  inc(e);
  map[e].v:=j;
  map[e].w:=w;
  map[e].next:=list[i];
  list[i]:=e;
  
  inc(e);
  map[e].v:=i;
  map[e].w:=w;
  map[e].next:=list[j];
  list[j]:=e;
end;

begin
  assign(input,'rebuild.in');
  reset(input);
  assign(output,'rebuild.out');
  rewrite(output);
  
  readln(n);
  readln(m);
  for i:=1 to m do
  begin
    readln(edge[i,1],edge[i,2],edge[i,3]);
    if edge[i,1]>edge[i,2] then
    begin
      y:=edge[i,1]; edge[i,1]:=edge[i,2]; edge[i,2]:=y;
    end;
  end;      
  sort(1,m);
  
  readln(m1);
  for i:=1 to m1 do
  begin
    readln(edge1[i,1],edge1[i,2]);
    if edge1[i,1]>edge1[i,2] then
    begin
      y:=edge1[i,1]; edge1[i,1]:=edge1[i,2]; edge1[i,2]:=y;
    end;
  end;  
  sort1(1,m1);
    
  j:=1;
  e:=0;
  for i:=1 to m do
    if (j>m1) or (edge[i,1]<>edge1[j,1]) or (edge[i,2]<>edge1[j,2]) then
      addedge(edge[i,1],edge[i,2],0)
    else
    begin
      addedge(edge[i,1],edge[i,2],edge[i,3]);
      inc(j);
    end;
  
  readln(ss,tt);
  fillchar(bb,sizeof(bb),false);
  fillchar(dist,sizeof(dist),0);
  fillchar(b,sizeof(b),false);
  h:=0;
  t:=1;
  q[1]:=ss;
  dist[ss]:=0;
  b[ss]:=true;
  bb[ss]:=true;
  while h<>t do
  begin
    h:=(h+1) mod n;
    i:=q[h];
    u:=list[i];
    while u<>0 do
    begin
      j:=map[u].v;
      if (not bb[j]) or (dist[i]+map[u].w<dist[j]) then
      begin
        dist[j]:=dist[i]+map[u].w;
        bb[j]:=true;
        if not b[j] then
        begin
          b[j]:=true;
          t:=(t+1) mod n;
          q[t]:=j;
        end;
      end;
      u:=map[u].next;
    end;
    b[i]:=false;
  end;
  writeln(dist[tt]);
  
  close(input);
  close(output);
end.