记录编号	49091	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	剑舞江南	是否通过	通过
代码语言	Pascal	运行时间	0.142 s
提交时间	2012-11-07 12:42:32	内存使用	1.92 MiB

Program PP1;
Var qi,mo,zh:array[1..20000]of longint;
    f,dist:array[1..210]of longint;
    q:array[1..400000]of longint;
    t:array[1..210]of boolean;
    w,l,n,m,x,y,z,head,tail,xx,i:longint;
Procedure qsort(s,t:longint);
  var i,j,mid,temp:longint;
  begin
  i:=s; j:=t; mid:=qi[(s+t)div 2];
  while i<=j do
    begin
      while qi[i]<mid do inc(i);
      while qi[j]>mid do dec(j);
      if i<=j then
        begin
        temp:=qi[i]; qi[i]:=qi[j]; qi[j]:=temp;
        temp:=mo[i]; mo[i]:=mo[j]; mo[j]:=temp;
        temp:=zh[i]; zh[i]:=zh[j]; zh[j]:=temp;
        inc(i); dec(j);
        end;
    end;
  if i<t then qsort(i,t);
  if j>s then qsort(s,j);
  end;
Begin
assign(input,'hardest.in'); reset(input);
assign(output,'hardest.out'); rewrite(output);
  readln(w);
  for l:=1 to w do begin
    fillchar(qi,sizeof(qi),0);
    fillchar(mo,sizeof(mo),0);
    fillchar(zh,sizeof(zh),0);
    fillchar(f,sizeof(f),0);
    readln(n,m);
    for i:=1 to m do begin
      readln(x,y,z);
      qi[2*i-1]:=x; mo[2*i-1]:=y; zh[2*i-1]:=z;
      qi[2*i]:=y; mo[2*i]:=x; zh[2*i]:=z;
    end;
    qsort(1,2*m);
    f[qi[1]]:=1; f[n+1]:=2*m+1;
    for i:=2 to 2*m do
      if qi[i]<>qi[i-1] then f[qi[i]]:=i;
    for i:=n downto 1 do
      if f[i]=0 then f[i]:=f[i+1];
    fillchar(q,sizeof(q),0);
    fillchar(t,sizeof(t),false);
    for i:=1 to 200 do dist[i]:=10000000;
    head:=0; tail:=1;
    q[1]:=1; t[1]:=true; dist[1]:=0;
    while head<=tail do begin
      inc(head); xx:=q[head];
      for i:=f[xx] to f[xx+1]-1 do
        if dist[mo[i]]>dist[xx]+zh[i] then begin
          dist[mo[i]]:=dist[xx]+zh[i];
          if t[mo[i]]=false then begin
            t[mo[i]]:=true;
            inc(tail);
            q[tail]:=mo[i];
          end;
        end;
      t[xx]:=false;
    end;
    if dist[n]=10000000 then writeln('-1') else writeln(dist[n]);
  end;
close(input);
close(output);
End.