记录编号	132075	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	传奇	是否通过	通过
代码语言	Pascal	运行时间	0.223 s
提交时间	2014-10-25 10:55:07	内存使用	0.82 MiB

program cojs1439;
type
  apoint=^node;
  node=record
    xb,data:longint;
    next:apoint;
  end;
  pnode=record
    qi,ho,x:longint;
  end;
var
  a:array[1..10000] of apoint;
  b:array[1..50000] of pnode;
  f:array[1..10000] of longint;
  fla:array[1..10000] of boolean;
  i,j,k,m,n,q:longint;
  f1,f2,a1,b1:longint;
function min(a,b:longint):longint;
begin
  if a<b then exit(a);
  exit(b);
end;

procedure qp(l,r:longint);
var
  i,j,x:longint;
  y:pnode;
begin
  i:=l; j:=r;
  x:=b[(l+r) div 2].x;
  repeat
    while x<b[i].x do inc(i);
    while x>b[j].x do dec(j);
    if i<=j then
      begin
        y:=b[i]; b[i]:=b[j]; b[j]:=y;
        inc(i); dec(j);
      end;
  until i>j;
  if j>l then qp(l,j);
  if i<r then qp(i,r);
end;
function find(x:longint):longint;
begin
  if f[x]=x then exit(x);
  f[x]:=find(f[x]);
  exit(f[x]);
end;
procedure add(l,r,x:longint);
var
  p:apoint;
begin
  new(p);
  p^.xb:=r;
  p^.data:=x;
  p^.next:=a[l];
  a[l]:=p;
end;
function bfs(l,r:longint):longint;
var
  dui:array[1..100000,1..2] of longint;
  i,j,k,front,tail:longint;
  p:apoint;
begin
  fillchar(fla,sizeof(fla),false);
  front:=0; tail:=1;
  dui[tail,1]:=l;
  dui[tail,2]:=maxlongint;
  fla[l]:=true;
  while front<tail do
    begin
      inc(front);
      p:=a[dui[front,1]];
      while p<>nil do
        begin
          if p^.xb=r then
            exit(min(p^.data,dui[front,2]));
          if not fla[p^.xb] then
            begin
              inc(tail);
              dui[tail,1]:=p^.xb;
              fla[p^.xb]:=true;
              dui[tail,2]:=min(p^.data,dui[front,2]);
            end;
          p:=p^.next;
        end;
    end;
  exit(-1);
end;
begin
  assign(input,'truck.in');
  assign(output,'truck.out');
  reset(input);
  rewrite(output);

  readln(n,m);
  for i:=1 to n do
    f[i]:=i;
  for i:=1 to m do
    readln(b[i].qi,b[i].ho,b[i].x);
  qp(1,m);

  for i:=1 to m do
    begin
      f1:=find(f[b[i].qi]);
      f2:=find(f[b[i].ho]);
      if f1<>f2 then
        begin
          add(b[i].qi,b[i].ho,b[i].x);
          add(b[i].ho,b[i].qi,b[i].x);
        end;
      f[f1]:=f2;
    end;
  readln(q);
  for i:=1 to q do
    begin
      readln(a1,b1);
      writeln(bfs(a1,b1));
    end;

  close(input);
  close(output);
end.