#include<cstdio>

#include<queue>

#include<cstring>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int MAXN=;

const int MAXM=;

typedef pair<long long,pair<int,int> > pii;

priority_queue<pii,vector<pii>,greater<pii> > q;

bool visit[MAXN][];

int pointer[MAXN];

long long d[MAXN][];

int n,m,k,tot=,S,T;

const long long INF=1e17;

struct Edge

{

    int to,next;

    long long w;

    Edge() {};

    Edge(int b,int nxt,int weight) {to=b,next=nxt,w=weight;}

}edge[MAXM];

inline void addedge(int a,int b,int w1)

{

    edge[tot]=Edge(b,pointer[a],w1);

    pointer[a]=tot++;

}

void dijkstra()

{

    rep(i,S,T) rep(z,,k) d[i][z]=INF;

    d[S][]=;

    memset(visit,,sizeof(visit));

    q.push(make_pair(d[S][],make_pair(S,)));

    while(!q.empty())

    {

        pii u=q.top();q.pop();

        int x=u.second.first,stp=u.second.second;

        if(visit[x][stp]) continue;

        visit[x][stp]=;

        for(int j=pointer[x];j!=-;j=edge[j].next)

        {

            int &v=edge[j].to;

            if(d[v][stp]>d[x][stp]+edge[j].w)

            {

                d[v][stp]=d[x][stp]+edge[j].w;

                q.push(make_pair(d[v][stp],make_pair(v,stp)));

            }

            if(stp<k&&d[v][stp+]>d[x][stp])

            {

                d[v][stp+]=d[x][stp];

                q.push(make_pair(d[v][stp+],make_pair(v,stp+)));

            }

        }

    }

}

void init()

{

    tot=;

    memset(pointer,-,sizeof(pointer));

}

void Input()

{

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

    int u,v;

    long long w;

    rep(i,,m)

    {

        scanf("%d%d%lld",&u,&v,&w);

        addedge(u,v,w);

    }

    S=;T=n;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int TT;

    scanf("%d",&TT);

    rep(tt,,TT)

    {

        init();

        Input();

        dijkstra();

        long long ans=INF;

        rep(i,,k) ans=min(ans,d[n][i]);

        printf("%lld\n",ans);

    }

    return ;

}