Your are given an undirect connected graph. Every edge has a cost to pass.
You should choose a path from $S$ to $T$ and you need to pay for all the edges in your path. However, you can choose at most $k$ edges in the graph and change their costs to zero in the beginning. 
Please answer the minimal total cost you need to pay.

The first line contains five integers $n,m,S,T,K$.
For each of the following m lines, there are three integers $a,b,l$, meaning there is an edge that costs $l$ between $a$ and $b$.
$n$ is the number of nodes and $m$ is the number of edges.

An integer meaning the minimal total cost.

$1≤n,m≤10^3,\ 1≤S,T,a,b≤n,\ 0≤k≤m,1≤l≤10^6$.
Multiple edges and self loops are allowed.