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;
 list: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
    for i:=0 to n-1 do
    if a[v,i]<maxlongint div 4-1 then
    if not o[i] then
     begin
      o[i]:=true;
      dfs1(i);
     end;
  inc(st[0]);st[st[0]]:=v;
 end;
 procedure dfs2(v:longint);
 var  i:longint;
 begin
  for i:=0 to n-1 do
  if i<>v then
  if a[i,v]<maxlongint div 4-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 3);
 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(o,sizeof(o),0);
 for i:=0 to n-1 do if not o[i] then dfs1(i);
 fillchar(o,sizeof(o),0);
 for l:=st[0] downto 1 do
  if not o[st[l]] then begin
   o[st[l]]:=true;
   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;list[1]:=0;
 fillchar(d,sizeof(d),$7f div 3);
 d[0,0]:=0;
 fillchar(o,sizeof(o),0);
 repeat
  inc(h);
  x:=list[h];
  o[h]:=false;
   for i:=0 to n-1 do
    begin
     if a[x,i]<maxlongint div 4-1 then
     begin
       for j:=0 to k do
        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 o[i] then
             begin
              inc(t);
              list[t]:=i;
              o[i]:=true;
             end;
           end;
         if c1[x,i]=1 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 o[i] then
             begin
              inc(t);
              list[t]:=i;
              o[i]:=true;
             end;
           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 4-1 then writeln(-1) else   writeln(ans);

 until 1>2;
 close(input);close(output); 
end.