记录编号	39056	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	wo shi 刘畅	是否通过	通过
代码语言	Pascal	运行时间	0.049 s
提交时间	2012-07-03 19:16:50	内存使用	15.67 MiB

const
  oo=maxlongint div 2;

var
  n,m,k,total,t,top,i,ans,j,num,x,y,z:longint;
  point,value,next,q:array[0..1000000]of longint;
  first,dfn,low,belong:array[0..10000]of longint;
  f:array[0..200,0..100]of longint;
  s,v:array[0..10000]of boolean;

procedure addpage(x,y,z:longint);
begin
  inc(total);
  point[total]:=y;
  value[total]:=z;
  next[total]:=first[x];
  first[x]:=total;
end;

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

procedure tarjan(u:longint);
var
  i,j:longint;
begin
  inc(t);
  dfn[u]:=t;
  low[u]:=t;
  inc(top);
  q[top]:=u;
  s[u]:=true;
  i:=first[u];
  while i>0 do
  begin
    j:=point[i];
    if dfn[j]=0 then
    begin
      tarjan(j);
      low[u]:=min(low[u],low[j]);
    end
    else if s[j] then low[u]:=min(low[u],dfn[j]);
    i:=next[i];
  end;
  if dfn[u]=low[u] then
  begin
    inc(num);
    repeat
      j:=q[top];
      belong[j]:=num;
      s[j]:=false;
      dec(top);
    until j=u;
  end;
end;

procedure spfa;
var
  h,t,i,x,y:longint;
begin
  h:=1;
  t:=1;
  q[t]:=1;
  repeat
    x:=q[h];
    i:=first[x];
    while i>0 do
    begin
      y:=point[i];

        if belong[x]=belong[y] then
        begin
          for j:=0 to k do
          if f[x,j]+value[i]<f[y,j] then
          begin
            f[y,j]:=f[x,j]+value[i];
            if not v[y] then
            begin
              v[y]:=true;
              inc(t);
              q[t]:=y;
            end;
          end;
        end
        else begin
          for j:=0 to k-1 do
          if f[x,j]+2*value[i]<f[y,j+1] then
          begin
            f[y,j+1]:=f[x,j]+2*value[i];
            if not v[y] then
            begin
              v[y]:=true;
              inc(t);
              q[t]:=y;
            end;
          end;
        end;
      i:=next[i];
    end;
    v[x]:=false;
    inc(h);
  until h>t;
end;

begin
  assign(input,'travela.in'); reset(input);
  assign(output,'travela.out'); rewrite(output);
  readln(n,m,k);
  while (n<>0)or(m<>0)or(k<>0) do
  begin
    total:=0;
    top:=0;
    for i:=1 to n do
    begin
      dfn[i]:=0;
      low[i]:=0;
      s[i]:=false;
      first[i]:=0;
    end;
    for i:=1 to m do
    begin
      readln(x,y,z);
      inc(x);
      inc(y);
      addpage(x,y,z);
    end;
    for i:=1 to n do
    if dfn[i]=0 then tarjan(i);

    for i:=1 to n do
     for j:=0 to k do
     f[i,j]:=oo;
	
    f[1,0]:=0;
    for i:=1 to n do v[i]:=false;
	v[1]:=true;
    spfa;
	ans:=oo;
	for j:=0 to k do
	if f[n,j]<ans then
	ans:=f[n,j];	
	if ans<oo then writeln(ans)
		else writeln(-1);
    readln(n,m,k);
  end;
end.