问题：给定一张有n个点，m条有向边的图。一个整数k。（n<=1e5,m<=2e5,k<=10）。你有k次机会使得图中的某一条边权值变为0。求1号点到n号点的最短距离。保证至少存在一条路径从1到n。

思路：dijkstra算法+dp转移

　　这其实就是一道分层最短路的模板题。普通的dijkstra算法，dis数组记录的是起点到该点的最短距离，这里的话多开一维就好了。dis[i][j]，代表起点到i点并且使用了j次机会的最短距离。转移时候分情况使用或不使用这次机会讨论来进行转移。因为k不超过10,所以空间复杂度和时间复杂度都是合理的。然后其他操作就和普通的dijkstra算法是一样的。具体见代码。

AC代码：

//#include<bits/stdc++.h>
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
inline ll lowbit(ll x) { return x & (-x); }
const double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
inline char nc() {
    static char buf[1 << 21], * p1 = buf, * p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline ll rd() {
    //#define getchar nc
    ll x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const double eps = 1e-6;
const int M = 1e6 + 10;
const int N = 1e5 + 10;
struct Edge {
    int to, next;
    ll w;
}e[N << 1];
int head[N];
int tot;
int n, m, k;
inline void add(int x, int y, ll w) {
    e[++tot] = { y,head[x],w };
    head[x] = tot;
}
ll dis[N][13];
bool vis[N][13];
struct MM {
    int node, use;
    ll val;
    bool friend operator<(const MM& m1, const MM& m2) {
        return m1.val > m2.val;
    }
};
priority_queue<MM>q;
inline ll dijkstra() {
    q.push({ 1,0 ,0 });
    dis[1][0] = 0;
    while (q.size()) {
        int x = q.top().node, use = q.top().use; q.pop();
        if (x == n) return dis[x][use];
        if (vis[x][use])continue;
        vis[x][use] = 1;
        for (int i = head[x]; i != -1; i = e[i].next) {
            int y = e[i].to;
            if (dis[y][use] > dis[x][use] + e[i].w) {//这一次不白嫖
                dis[y][use] = dis[x][use] + e[i].w;
                q.push({ y,use,dis[y][use] });
            }
            if (use < k && dis[y][use + 1] > dis[x][use]) {//这次白嫖
                dis[y][use + 1] = dis[x][use];
                q.push({ y,use + 1,dis[y][use + 1] });
            }
        }
    }
}
void init() {
    tot = 0;
    memset(head, -1, sizeof(head[0]) * (n + 5));
    memset(dis, INF, sizeof(dis[0]) * (n + 5));
    memset(vis, 0, sizeof(vis[0]) * (n + 5));
    while (q.size())q.pop();
}
int main() {
    int t = rd();
    while (t--) {
        n = rd(), m = rd(), k = rd();
        init();
        while (m--) {
            int u = rd(), v = rd();
            ll w = rd();
            add(u, v, w);
        }
        printf("%lld\n", dijkstra());
    }
}