×

# 计蒜客

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

• main.c