类似于2763，不过层与层之间的边权要改为原边权的一半。我直接改了这个细节贴2763的代码了。
program p2662;
type
bian=record
next,point,w:longint;
end;
heap=record
dis,point:longint;
end;
var
p,d:array[1..200000] of longint;
x:array[1..200000] of heap;
b:array[1..1500000] of bian;
ans,len,s,t,n,m,k,i,j,k1,k2,k3,maxn:longint;
now:heap;
procedure ade(k1,k2,k3:longint);
begin
inc(len);
b[len].point:=k2;
b[len].w:=k3;
b[len].next:=p[k1];
p[k1]:=len;
end;
procedure add(k1,k2,k3:longint);
begin
ade(k1,k2,k3);
ade(k2,k1,k3);
end;
function minn(k1,k2:longint):longint;
begin
if x[k1].dis<=x[k2].dis then exit(k1) else exit(k2);
end;
function min(k1,k2,k3:longint):longint;
begin
exit(minn(k1,minn(k2,k3)));
end;
procedure press(k:longint);
var
i:longint;
j:heap;
begin
i:=min(k,k*2,k*2+1);
if i=k then exit;
j:=x[k]; x[k]:=x[i]; x[i]:=j;
press(i);
end;
procedure find(k:longint);
var
i:heap;
begin
if k=1 then exit;
if x[k].dis<x[k div 2].dis then begin
i:=x[k];
x[k]:=x[k div 2];
x[k div 2]:=i;
find(k div 2);
end;
end;
procedure push(k:heap);
var
i,j:longint;
begin
i:=p[k.point];
while i<>0 do begin
j:=b[i].point;
if k.dis+b[i].w<d[j] then begin
d[j]:=k.dis+b[i].w;
inc(len);
x[len].point:=j;
x[len].dis:=d[j];
find(len);
end;
i:=b[i].next;
end;
end;
begin
readln(n,m,k);
len:=0;
fillchar(p,sizeof(p),0);
fillchar(b,sizeof(b),0);
for i:=1 to m do begin
readln(k1,k2,k3);
add(k1,k2,k3);
for j:=0 to k-1 do begin
ade(j*n+k1,j*n+n+k2,k3 div 2);
ade(j*n+k2,j*n+k1+n,k3 div 2);
add(j*n+n+k1,j*n+n+k2,k3);
end;
end;
fillchar(d,sizeof(d),$3f);
fillchar(x,sizeof(x),$7f);
maxn:=x[1].dis;
s:=1; t:=n;
len:=1; x[1].point:=s; d[s]:=0; x[1].dis:=0;
while len>0 do begin
dec(len);
now:=x[1];
if len>0 then begin
x[1]:=x[len+1];
x[len+1].dis:=maxn;
press(1);
end;
push(now);
end;
ans:=maxlongint;
for i:=0 to k do
if d[i*n+t]<ans then ans:=d[i*n+t];
writeln(ans);
end.
