记录编号	39039	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	isabella	是否通过	通过
代码语言	Pascal	运行时间	0.056 s
提交时间	2012-07-03 17:23:54	内存使用	0.21 MiB

const maxn=1000000000;
var
 map:array[0..100,0..100]of longint;
 v:array[0..100]of boolean;
 zhan,fa:array[0..100]of longint;
 f:array[0..100,0..10]of longint;
 i,j,m,n,k,l,a,b,top,t,h,ans:longint;
 flag:boolean;

 function father(x:longint):longint;
  begin
   if fa[x]=x then exit(x);
   fa[x]:=father(fa[x]);
   exit(fa[x]);
  end;

 procedure hebing(x,y:longint);
  var i,j:longint;
  begin
   i:=father(x);j:=father(y);
   fa[i]:=j;
  end;

 procedure bianli(x:longint);
  var i:longint;
  begin
   v[x]:=true;
   for i:=0 to n-1 do
    if (map[x,i]<maxn)and(v[i]=false) then bianli(i);
   inc(top);zhan[top]:=x;
  end;

 procedure find(x:longint);
  var i:longint;
  begin
   v[x]:=true;
   for i:=0 to n-1 do
    if (map[i,x]<maxn)and(v[i]=false) then
     begin hebing(x,i);find(i);end;
  end;

 function min(a,b:longint):longint;
 begin if a<b then exit(a) else exit(b);end;

begin
assign(input,'travela.in');reset(input);
assign(output,'travela.out');rewrite(output);
 readln(n,m,k);
 while not((n=0)and(m=0)and(k=0))do
 begin
 fillchar(map,sizeof(map),$3f);
 fillchar(f,sizeof(f),$3f);

 for i:=0 to n-1 do fa[i]:=i;
 for i:=1 to m do
  begin
   read(a,b,l);
   if map[a,b]>l*2 then map[a,b]:=l*2;
  end;

 top:=0;fillchar(v,sizeof(v),0);
 bianli(0);
 if v[n-1]=false then begin
  writeln(-1);close(input);close(output);halt;
 end;

 fillchar(v,sizeof(v),0);
 for i:=top downto 1 do
  if v[zhan[i]]=false then find(zhan[i]);

 for i:=0 to n-1 do j:=father(i);

 for h:=0 to k do f[n-1,h]:=0;

 for l:=1 to n do
 begin
  flag:=false;
  for i:=0 to n-1 do
   for j:=0 to n-1 do
    if (i<>j)and(map[i,j]<maxn) then
     begin
      if fa[i]=fa[j] then begin
       t:=map[i,j]div 2;
       for h:=0 to k do
        if f[i,h]>f[j,h]+t then begin f[i,h]:=f[j,h]+t;flag:=true;end;
      end
      else begin
       t:=map[i,j];
       for h:=0 to k-1 do
        if f[i,h+1]>f[j,h]+t then begin f[i,h+1]:=f[j,h]+t;flag:=true;end;
      end;
     end;
   if flag=false then break;
  end;

 ans:=maxlongint;
 for h:=0 to k do ans:=min(ans,f[0,h]);
 if ans<maxn then writeln(ans) else writeln(-1);

 readln(n,m,k);
 end;
close(input);close(output);
end.