/*__ _(_) __ _ ___ ___ _ _ __| | __ _ _ _| |_ ___
/ _` | |/ _` |/ _ \/ __| | | |/ _` |/ _` | | | | __/ _ \
| (_| | | (_| | (_) \__ \ |_| | (_| | (_| | |_| | || (_) |
\__, |_|\__,_|\___/|___/\__,_|\__,_|\__,_|\__,_|\__\___/
|___/ Accepted Code */
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
for (scanf("%d",&T); T--;)
{
int N, M, C;
int next[222][222], w[222][222];
memset(next,0,sizeof(next));
scanf("%d%d%d",&N,&M,&C);
for (int i=1; i<=M; i++)
{
int x,y,l;
scanf("%d%d%d",&x,&y,&l); // Biểu diễn đồ thì bàng danh sách kề
next[x][++next[x][0]]=y; // next[x][0] là số đỉnh kề với đỉnh x
next[y][++next[y][0]]=x; // next[x][i] là các đỉnh kề với x (0<=i<=next[x][0])
w[x][y]=w[y][x]=l; // Độ dài đường đi nối giữa x,y và y,x
}
bool visited[222];
memset(visited,false,sizeof(visited));
int dp[222];
for(int i=0; i<222; i++) dp[i]=INT_MAX;
dp[N]=0;
while (true)
{
int u=1; // tìm nơi cần ít nước nhất, ban đầu giả sử là 1
for(int i=2; i<=N; i++)
if(visited[i]==false && dp[u]>dp[i]) u=i;
visited[u]=true; // đánh dấu đỉnh này đã thăm
if(u==1) break; // Khi đã về đến 1 thì dừng lại
for(int i=1; i<=next[u][0]; i++)
{
int v=next[u][i]; // đỉnh kề với đỉnh u
if(visited[v])continue; // nếu đã thăm rồi thì bỏ qua
int need=dp[u]; // lượng nước cần mang tới đỉnh u
int L=w[u][v]; // Độ dài đoạn đường nối từ u đến v
int water; // Lượng nước mà đỉnh v tối thiểu cần có
if(need+L<=C) water=need+L;
else
{
if(C<=2*L)continue; //Nếu không đủ sức mang nước đi và về thì coi như không có cạnh nối đỉnh u và v
int t=(need+L-C)/(C-2*L); //Số luợt đi và về
if((need+L-C)%(C-2*L)>0) t++;
water=(2*t+1)*L+need;
}
dp[v]=min(dp[v],water); //Tối ưu lại lượng nước tối thiểu cần dùng ở đỉnh v
}
}
printf("%d\n",dp[1]);
}
return 0;
}
LypfXyBfKF8pIF9fIF8gIF9fXyAgX19fIF8gICBfICBfX3wgfCBfXyBfIF8gICBffCB8XyBfX18KIC8gX2AgfCB8LyBfYCB8LyBfIFwvIF9ffCB8IHwgfC8gX2AgfC8gX2AgfCB8IHwgfCBfXy8gXyBcCnwgKF98IHwgfCAoX3wgfCAoXykgXF9fIFwgfF98IHwgKF98IHwgKF98IHwgfF98IHwgfHwgKF8pIHwKIFxfXywgfF98XF9fLF98XF9fXy98X19fL1xfXyxffFxfXyxffFxfXyxffFxfXyxffFxfX1xfX18vCiB8X19fLyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBBY2NlcHRlZCBDb2RlICAqLwojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkKewogICAgaW50IFQ7CiAgICBmb3IgKHNjYW5mKCIlZCIsJlQpOyBULS07KQogICAgewogICAgICAgIGludCBOLCBNLCBDOwogICAgICAgIGludCBuZXh0WzIyMl1bMjIyXSwgd1syMjJdWzIyMl07CiAgICAgICAgbWVtc2V0KG5leHQsMCxzaXplb2YobmV4dCkpOwogICAgICAgIHNjYW5mKCIlZCVkJWQiLCZOLCZNLCZDKTsKICAgICAgICBmb3IgKGludCBpPTE7IGk8PU07IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGludCB4LHksbDsKICAgICAgICAgICAgc2NhbmYoIiVkJWQlZCIsJngsJnksJmwpOyAvLyBCaeG7g3UgZGnhu4VuIMSR4buTIHRow6wgYsOgbmcgZGFuaCBzw6FjaCBr4buBCiAgICAgICAgICAgIG5leHRbeF1bKytuZXh0W3hdWzBdXT15OyAvLyBuZXh0W3hdWzBdIGzDoCBz4buRIMSR4buJbmgga+G7gSB24bubaSDEkeG7iW5oIHgKICAgICAgICAgICAgbmV4dFt5XVsrK25leHRbeV1bMF1dPXg7IC8vIG5leHRbeF1baV0gbMOgIGPDoWMgxJHhu4luaCBr4buBIHbhu5tpIHggKDA8PWk8PW5leHRbeF1bMF0pCiAgICAgICAgICAgIHdbeF1beV09d1t5XVt4XT1sOyAvLyDEkOG7mSBkw6BpIMSRxrDhu51uZyDEkWkgbuG7kWkgZ2nhu69hIHgseSB2w6AgeSx4CiAgICAgICAgfQoKICAgICAgICBib29sIHZpc2l0ZWRbMjIyXTsKICAgICAgICBtZW1zZXQodmlzaXRlZCxmYWxzZSxzaXplb2YodmlzaXRlZCkpOwogICAgICAgIGludCBkcFsyMjJdOwogICAgICAgIGZvcihpbnQgaT0wOyBpPDIyMjsgaSsrKSBkcFtpXT1JTlRfTUFYOwoKICAgICAgICBkcFtOXT0wOwogICAgICAgIHdoaWxlICh0cnVlKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHU9MTsgLy8gdMOsbSBuxqFpIGPhuqduIMOtdCBuxrDhu5tjIG5o4bqldCwgYmFuIMSR4bqndSBnaeG6oyBz4butIGzDoCAxCiAgICAgICAgICAgIGZvcihpbnQgaT0yOyBpPD1OOyBpKyspCiAgICAgICAgICAgICAgICBpZih2aXNpdGVkW2ldPT1mYWxzZSAmJiBkcFt1XT5kcFtpXSkgdT1pOwogICAgICAgICAgICB2aXNpdGVkW3VdPXRydWU7IC8vIMSRw6FuaCBk4bqldSDEkeG7iW5oIG7DoHkgxJHDoyB0aMSDbQogICAgICAgICAgICBpZih1PT0xKSBicmVhazsgLy8gS2hpIMSRw6MgduG7gSDEkeG6v24gMSB0aMOsIGThu6tuZyBs4bqhaQogICAgICAgICAgICBmb3IoaW50IGk9MTsgaTw9bmV4dFt1XVswXTsgaSsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbnQgdj1uZXh0W3VdW2ldOyAvLyDEkeG7iW5oIGvhu4EgduG7m2kgxJHhu4luaCB1CiAgICAgICAgICAgICAgICBpZih2aXNpdGVkW3ZdKWNvbnRpbnVlOyAvLyBu4bq/dSDEkcOjIHRoxINtIHLhu5NpIHRow6wgYuG7jyBxdWEKICAgICAgICAgICAgICAgIGludCBuZWVkPWRwW3VdOyAvLyBsxrDhu6NuZyBuxrDhu5tjIGPhuqduIG1hbmcgdOG7m2kgxJHhu4luaCB1CiAgICAgICAgICAgICAgICBpbnQgTD13W3VdW3ZdOyAvLyDEkOG7mSBkw6BpIMSRb+G6oW4gxJHGsOG7nW5nIG7hu5FpIHThu6sgdSDEkeG6v24gdgogICAgICAgICAgICAgICAgaW50IHdhdGVyOyAvLyBMxrDhu6NuZyBuxrDhu5tjIG3DoCDEkeG7iW5oIHYgdOG7kWkgdGhp4buDdSBj4bqnbiBjw7MKICAgICAgICAgICAgICAgIGlmKG5lZWQrTDw9Qykgd2F0ZXI9bmVlZCtMOwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmKEM8PTIqTCljb250aW51ZTsgLy9O4bq/dSBraMO0bmcgxJHhu6cgc+G7qWMgbWFuZyBuxrDhu5tjIMSRaSB2w6AgduG7gSB0aMOsIGNvaSBuaMawIGtow7RuZyBjw7MgY+G6oW5oIG7hu5FpIMSR4buJbmggdSB2w6AgdgogICAgICAgICAgICAgICAgICAgIGludCB0PShuZWVkK0wtQykvKEMtMipMKTsgLy9T4buRIGx14bujdCDEkWkgdsOgIHbhu4EKICAgICAgICAgICAgICAgICAgICBpZigobmVlZCtMLUMpJShDLTIqTCk+MCkgdCsrOwogICAgICAgICAgICAgICAgICAgIHdhdGVyPSgyKnQrMSkqTCtuZWVkOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZHBbdl09bWluKGRwW3ZdLHdhdGVyKTsgLy9U4buRaSDGsHUgbOG6oWkgbMaw4bujbmcgbsaw4bubYyB04buRaSB0aGnhu4N1IGPhuqduIGTDuW5nIOG7nyDEkeG7iW5oIHYKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBwcmludGYoIiVkXG4iLGRwWzFdKTsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==