var
  i,j,k,n,m,min,ans,l,o,x,y,z:longint;
  a,b:array[0..100,0..100] of longint;
  ok:array[0..100,0..100] of boolean;
  c:array[0..100,0..100,0..100] of longint;
begin
  assign(input,'travela.in'); reset(input);
  assign(output,'travela.out'); rewrite(output);
  readln(n,m,min);
  fillchar(a,sizeof(a),$7F div 4);
  for i:=0 to n-1 do a[i,i]:=0;
  for i:=1 to m do
    begin
      readln(x,y,z);
      if a[x,y]>z then
        a[x,y]:=z;
    end;
  b:=a;
  for k:=0 to n-1 do
    for i:=0 to n-1 do
      for j:=0 to n-1 do
        if a[i,k]+a[k,j]<a[i,j] then
          a[i,j]:=a[i,k]+a[k,j];
  for i:=0 to n-1 do
    for j:=i to n-1 do
      if (a[i,j]<100000000)and(a[j,i]<100000000) then
        begin
          ok[i,j]:=true;
          ok[j,i]:=true;
        end;
  fillchar(c,sizeof(c),$7F div 2);
  for i:=0 to n-1 do
    for j:=i to n-1 do
      if ok[i,j]=false then
        begin
          c[1,i,j]:=b[i,j]*2;
          c[1,j,i]:=b[j,i]*2;
        end
        else
        begin
          c[0,i,j]:=b[i,j];
          c[0,j,i]:=b[j,i];
        end;
  for k:=0 to n-1 do
    for i:=0 to n-1 do
      for j:=0 to n-1 do
        for l:=0 to min do
          for o:=0 to l do
            if c[o,i,k]+c[l-o,k,j]<c[l,i,j] then
              c[l,i,j]:=c[o,i,k]+c[l-o,k,j];
  ans:=maxlongint;
  for i:=0 to min do
    if ans>c[i,0,n-1] then ans:=c[i,0,n-1];
  if ans>100000000 then writeln(-1) else writeln(ans);
  close(input); close(output);
end.