There are $N$ cities in the country, and $M$ directional roads from $u \to v\ (1≤u,v≤n)$. Every road has a distance $c_i$. 
Haze is a Magical Girl that lives in City $1$, she can choose no more than $K$ roads and make their distances become $0$. 
Now she wants to go to City $N$, please help her calculate the minimum distance.

The first line has one integer $T\ (1≤T≤5)$, then following $T$ cases.
For each test case, the first line has three integers $N,M, K$.
Then the following $M$ lines each line has three integers, describe a road, $u_i,v_i,c_i$. 
There might be multiple edges between $u$ and $v$.
It is guaranteed that $N≤100,000,\ M≤200,000,\ K≤10,\ 0 \leq c_i≤10^9$. 
There is at least one path between City $1$ and City $N$.

For each test case, print the minimum distance.