const
  oo=maxlongint;

var
  n,m,k,i,j:longint;
  g,gz,a,az:array[0..50000,0..50]of longint;
  v:Array[0..50000]of boolean;
  d,q:array[0..1000000]of longint;
  f:array[0..50000,0..10]of longint;

procedure init;
var
  i,x,y,z:longint;
begin
  assign(input,'slide.in'); reset(input);
  assign(output,'slide.out'); rewrite(output);
  readln(n,m,k);
  for i:=1 to m do
  begin
    readln(x,y,z);
    inc(g[x,0]);
    g[x,g[x,0]]:=y;

    inc(gz[x,0]);
    gz[x,gz[x,0]]:=z;

    inc(a[y,0]);
    a[y,a[y,0]]:=x;

    inc(az[y,0]);
    az[y,az[y,0]]:=z;
  end;
end;

procedure spfa;
var
  h,x,i,t,y:longint;
begin
  h:=1;
  t:=1;
  q[1]:=n;
  for i:=1 to n do d[i]:=0;

  repeat
    x:=q[h];
    for i:=1 to a[x,0] do
    begin
      y:=a[x,i];
      if d[x]+az[x,i]>d[y] then
      begin
        d[y]:=d[x]+az[x,i];
        inc(t);
        q[t]:=y;
      end;
    end;
    inc(h);
  until h>t;
end;

function min(x,y:longint):longint;
begin
  if x<y then exit(x);
  exit(y);
end;

function go(i,j:longint):longint;
var
  p,ans,y:longint;
begin
  if j=0 then
  begin
    f[i,j]:=d[i];
    exit(f[i,j]);
  end;
  if i=n then
  begin
    f[n,j]:=0;
    exit(0);
  end;
  if f[i,j]>0 then exit(f[i,j]);

  ans:=oo;
  for p:=1 to g[i,0] do
  begin
    y:=g[i,p];
    ans:=min(ans,gz[i,p]+go(y,j-1));
  end;

  f[i,j]:=ans;
  exit(ans);
end;

begin
  init;
  spfa;
  writeln(go(1,k));
  close(input);
  close(output);
end.