program main;
type
  integer=longint;
const
  maxn=110;
  maxm=101000;
  maxk=12;
var
  n,m,k:integer;
  ver:array[1..maxn] of integer;
  en,next:array[1..maxm] of integer;
  l:array[1..maxm] of integer;
  dfn,low:array[1..maxn] of integer;
  stack:array[1..maxn] of integer;
  instack:array[1..maxn] of boolean;
  tick:array[1..maxn] of integer;
  time,tot,sl:integer;
  mark:array[1..maxn,0..maxk] of boolean;
  d:array[1..maxn,0..maxk] of integer;
  Q:array[1..maxn*maxk*10,1..2] of integer;

  procedure Fopen;
  begin
    assign(input,'travela.in');
    assign(output,'travela.out');
    reset(input);
    rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input);
    close(output);
  end;
  procedure SetGraph;
  var
    i:integer;
    u,v,c:integer;
  begin
    fillchar(ver,sizeof(ver),0);
    fillchar(next,sizeof(next),0);
    for i:=1 to m do
    begin
      readln(u,v,c);
      inc(u); inc(v);
      en[i]:=v; next[i]:=ver[u]; ver[u]:=i;
      l[i]:=c;
    end;
  end;

  procedure DFS(u:integer);
  var
    i,v:integer;
  begin
    inc(time);
    dfn[u]:=time; low[u]:=time;
    inc(sl); stack[sl]:=u;
    instack[u]:=true;
    i:=ver[u];
    while i>0 do
    begin
      v:=en[i];
      if dfn[v]=0 then
      begin
        DFS(v);
        if low[v]<low[u] then low[u]:=low[v];
      end else if instack[v] then
      begin
        if dfn[v]<low[u] then low[u]:=dfn[v];
      end;
      i:=next[i];
    end;
    if dfn[u]=low[u] then
    begin
      inc(tot);
      while stack[sl]<>u do
      begin
        tick[stack[sl]]:=tot;
        instack[stack[sl]]:=false;
        dec(sl);
      end;
      tick[u]:=tot;
      instack[u]:=false;
      dec(sl);
    end;
  end;

  procedure Tarjan;
  var
    i:integer;
  begin
    fillchar(dfn,sizeof(dfn),0);
    fillchar(low,sizeof(low),0);
    fillchar(instack,sizeof(instack),false);
    time:=0; tot:=0; sl:=0;
    for i:=1 to n do if dfn[i]=0 then DFS(i);
    while sl>0 do
    begin
      inc(tot);
      tick[stack[sl]]:=tot;
      dec(sl);
    end;
  end;

  procedure Spfa;
  var
    head,tail:integer;
    i,j,u,v,step:integer;
    min:integer;
  begin
    for i:=1 to n do
      for j:=0 to k do d[i,j]:=maxlongint shr 2;
    d[1,0]:=0;
    fillchar(mark,sizeof(mark),true);
    mark[1,0]:=false;
    head:=1; tail:=2;
    Q[1,1]:=1; Q[1,2]:=0;
    repeat
      u:=Q[head,1]; step:=Q[head,2];
      i:=ver[u];
      while i>0 do
      begin
        v:=en[i];
        if tick[u]=tick[v] then
        begin
          if d[u,step]+l[i]<d[v,step] then
          begin
            d[v,step]:=d[u,step]+l[i];
            if mark[v,step] then
            begin
              mark[v,step]:=false;
              Q[tail,1]:=v; Q[tail,2]:=step;
              inc(tail);
            end;
          end;
        end else if step<k then
        begin
          if d[u,step]+l[i] shl 1<d[v,step+1] then
          begin
            d[v,step+1]:=d[u,step]+l[i] shl 1;
            if mark[v,step+1] then
            begin
              mark[v,step+1]:=false;
              Q[tail,1]:=v; Q[tail,2]:=step+1;
              inc(tail);
            end;
          end;
        end;
        i:=next[i];
      end;
      mark[u,step]:=true;
      inc(head);
    until head=tail;
    min:=maxlongint shr 2;
    for i:=0 to k do
      if d[n,i]<min then min:=d[n,i];
    if min<maxlongint shr 2 then writeln(min) else writeln(-1);
  end;
begin
  Fopen;
  repeat
    readln(n,m,k);
    if (n=0) and (m=0) and (k=0) then break;
    SetGraph;
    Tarjan;
    Spfa;
  until false;
  Fclose;
end.