Booster

Bob drives from his house to his office every day. The two are far apart, so he crosses several districts on the way, and he always takes the fastest route on the street map he keeps. One day traffic held him up and he arrived late. His boss put him on probation and told him that arriving late once more costs him the job. Bob has worried about it day and night ever since.

Alice knows the situation, so she built boosters for Bob's car. A booster makes the car run twice as fast, but it shuts off the moment the car turns or slows down. One booster therefore works on exactly one street, and it is used up once Bob has driven that street. Two boosters cannot be spent on the same street. A street that takes $T$ minutes takes $\lfloor T/2 \rfloor$ minutes with a booster on it.

Today the traffic is the worst it has ever been. Bob has $K$ boosters and may use some of them or all of them. His house is district 1 and his office is district $N$. Take the shortest travel time with no booster and subtract the shortest travel time Bob can reach when the boosters are placed as well as possible. That difference is how many minutes he saves today.

The first line contains the number of test cases $C$.

The first line of each test case holds three integers $N$, $M$, and $K$ ($1 \le N \le 5\,000$, $1 \le M \le 100\,000$, $1 \le K \le 100$), the number of districts, the number of streets, and the number of boosters Bob has.

Each of the next $M$ lines describes one street with three integers $X$, $Y$, and $T$ ($1 \le X, Y \le N$, $2 \le T \le 100\,000$). The street connects district $X$ and district $Y$, and driving it takes $T$ minutes. Every street is two way, so Bob may drive it in either direction. No two streets connect the same pair of districts. A route from district 1 to district $N$ always exists.

Print one line per test case, holding a single integer. It is the largest amount of time Bob can save with at most $K$ boosters, that is, the shortest travel time without boosters minus the shortest travel time he can reach by placing the boosters.