ll@n,@m,@k,@c[m];
int@(u,v)[m]--;
wgraph<ll>g;
g.setEdge(n,m,u,v,c);
DijkstraHeap<ll>h;
h.malloc(4n,1);
rep(i,k+1){
	h.change(i,0);
}
while(h.size){
	ll x=h.pop();
	rep(j,g.es[x/4]){
		ll y=g.edge[x/4][j]*4+x%4;
		h.change(y,h.val[x]+g.cost[x/4][j]);
		if(x%4<k){
			h.change(y+1,h.val[x]);
		}
	}
}
wt(h.visited[(n-1)*4+k]?h.val[(n-1)*4+k]:-1);