×

- 18.41%
- 262144K

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.