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

VAR
 d:array[0..110,0..10] of longint;
 st,f:array[0..1111] of longint;
 a,c1:array[0..110,0..110] of longint;
 o:array[0..1100] of boolean;
 ox:array[0..110,0..10] of boolean;
 list1,list2:array[1..3111111] of longint;
 bx,by,bz:array[0..110000] of longint;
 i,j,m,n,k,xx,yy,zz,h,t,x,ans,l,long:longint;
 procedure dfs1(v:longint);
 var  i:longint;
 begin
 o[v]:=true;
    for i:=0 to n-1 do
    if a[v,i]<maxlongint div 3-1 then
    if not o[i] then
     begin
      dfs1(i);
     end;
  inc(st[0]);st[st[0]]:=v;
 end;
 procedure dfs2(v:longint);
 var  i:longint;
 begin
 o[v]:=true;
  for i:=0 to n-1 do
  if i<>v then
  if a[i,v]<maxlongint div 3-1 then
    if not o[i] then
     begin
      o[i]:=true;
      dfs2(i);
     end;
  f[v]:=long;
 end;
 begin
 assign(input,'travela.in');reset(input);
 assign(output,'travela.out');rewrite(output);
 repeat
 readln(n,m,k);
 if n=0 then break;
 fillchar(a,sizeof(a),$7f div 2);
 for i:=1 to m do
  begin
   readln(bx[i],by[i],bz[i]);
   if a[bx[i],by[i]]>bz[i] then
   a[bx[i],by[i]]:=bz[i];
  end;
 fillchar(c1,sizeof(c1),0);
 fillchar(o,sizeof(o),0);
 st[0]:=0;
 for i:=0 to n-1 do if not o[i] then dfs1(i);
 fillchar(o,sizeof(o),0);
 long:=0;
 for l:=st[0] downto 1 do
  if not o[st[l]] then begin
   inc(long);
   dfs2(st[l]);
   end;
 for i:=1 to m do
  if f[bx[i]]<>f[by[i]] then c1[bx[i],by[i]]:=1;
 h:=0;t:=1;list1[1]:=0;list2[1]:=0;
 fillchar(d,sizeof(d),$7f div 2);
 d[0,0]:=0;
 fillchar(ox,sizeof(ox),0);
 repeat
  inc(h);
  x:=list1[h];
  j:=list2[h];
  ox[x,j]:=false;
   for i:=0 to n-1 do
    begin
     if a[x,i]<maxlongint div 3-1 then
     begin
         if c1[x,i]=0 then
          if d[x,j]+a[x,i]<d[i,j] then
           begin
            d[i,j]:=d[x,j]+a[x,i];
            if not ox[i,j] then
             begin
              inc(t);
              list1[t]:=i;
              list2[t]:=j;
              ox[i,j]:=true;
             end;
           end;
         if c1[x,i]=1 then
         if j+1<=k then
          if d[x,j]+a[x,i]*2<d[i,j+1] then
            begin
            d[i,j+1]:=d[x,j]+a[x,i]*2;
            if not ox[i,j+1] then
             begin
              inc(t);
              list1[t]:=i;
              list2[t]:=j+1;
              ox[i,j+1]:=true;
             end;
           end;
     end;
   end;
 until h>=t;
 ans:=maxlongint;
 for i:=0 to k do
 if d[n-1,i]<ans then ans:=d[n-1,i];
 if ans>maxlongint div 3-1 then writeln(-1) else writeln(ans);
 until 1>2;
 close(input);close(output);
end.