×

计蒜客

  1. 题库
  2. Magical Girl Haze
  3. 问答
  • 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.

Input

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$.

Output

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

样例输出

3

题目来源

ACM-ICPC 2018 南京赛区网络预赛

想挑战这道题吗

  • main.c