#include <bits/stdc++.h>

using namespace std;
long long q,m,n=0,c,u,v,w,price[222];
vector<pair<int,long long> >l[222];
struct cmp{
    bool operator()(pair<int,long long>x,pair<int,long long>y)
    {
        return x.second>y.second;
    }
};
priority_queue<pair<int,long long>,vector<pair<int,long long> >,cmp>s;
pair<int,long long>tam,temp;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>q;
    while(q--)
    {
        for(int i=1; i<222; i++)
            l[i].clear();
        cin>>n>>m>>c;
        for(int i=1; i<=n; i++)
            price[i]=1e18;
        for(int i=1; i<=m; i++)
        {
            cin>>u>>v>>w;
            l[u].push_back({v,w});
            l[v].push_back({u,w});
        }
        price[n]=0;
        s.push({n,0});
        while(!s.empty())
        {
            tam=s.top();
            s.pop();
            if(tam.second!=price[tam.first])continue;
            u=tam.first;
            for(int i=0; i<l[u].size(); i++)
            {
                temp=l[u][i];
                long long need=tam.second,ca=temp.second;
                if(need+ca<=c)temp.second=need+ca;
                else
                {
                    if(c<=2*ca)continue;
                    long long t=(need+ca-c)/(c-2*ca);
                    if((need+c-ca)%(c-2*ca)!=0)t++;
                    temp.second=(2*t+1)*ca+need;
                }
                if(price[temp.first]>temp.second)
                {
                    price[temp.first]=temp.second;
                    s.push(temp);
                }
            }
        }
        cout<<price[1]<<'\n';
    }
    return 0;
}