There are $N$ cities in the country, and $M$ directional roads from $u$ to $v(1\le u, v\le 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 \le T\le 5)$, then following $T$ cases.
For each test case, the first line has three integers $N, M$ and $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 \le 100000, M \le 200000, K \le 10$,
$0 \le C_i \le 1e9$. There is at least one path between City $1$ and City $N$.
For each test case, print the minimum distance.
1 5 6 1 1 2 2 1 3 4 2 4 3 3 4 1 3 5 6 4 5 2