#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

int dist[maxn];

struct node{

    int id, d;

    node(){}

    node(int a,int b) {id = a; d = b;}

    bool operator < (const node & a)const{

        if(d == a.d) return id > a.id;

        else return d > a.d;

    }

};

vector<node>e[maxn];

int n;

void dijkstra(int s){

    for(int i = ; i <= n; i++) dist[i] = inf;

    dist[s] = ;

    priority_queue<node>q;

    q.push(node(s, dist[s]));

    while(!q.empty()){

        node top = q.top();

        q.pop();

        if(top.d != dist[top.id]) continue;

        for(int i = ; i < (int)e[top.id].size(); i++){

            node x = e[top.id][i];

            if(dist[x.id] > top.d + x.d){

                dist[x.id] = top.d + x.d;

                q.push(node(x.id, dist[x.id]));

            }

        }

    }

    return;

}

int main() {

    int T;

    scanf("%d", &T);

    while(T--){

        int m, k;

        scanf("%d %d %d", &n, &m, &k);

        while(m--){

            int x ,y, w;

            scanf("%d %d %d", &x, &y, &w);

            for(int i = ; i <= k; i++){

                e[x + i*n].pb(node(y + i*n, w));

                if(i)e[x + (i-)*n].pb(node(y + i*n, ));

            }

        }

        n += k*n;

        dijkstra();

        printf("%d\n", dist[n]);

        for(int i = ; i <= n; i++)e[i].clear();

    }

    return ;

}