#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN=25010;
int t,n,m,o;
struct N{
	ll y,v;
	bool operator<(const N &n1)const{
		return v>n1.v;
	}
};
vector<N> e[NN];
ll dis[NN][2];
bool vis[NN][2];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t>>t;
	while(t--){
		memset(e,0,sizeof(e));
		cin>>n>>m>>o;
		for(int i=1,x,y,v;i<=m;i++){
			cin>>x>>y>>v;
			e[x].push_back({y,v});
			e[y].push_back({x,v});
		}
		ll mn=1e9;
		for(N i:e[1])mn=min(mn,i.v);
		if(mn>1){
			cout<<"-1\n";
			continue;
		}
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		priority_queue<N> q;
		q.push({1,0});
		dis[1][0]=0;
		while(!q.empty()){
			N t=q.top();
			q.pop();
			if(vis[t.y][t.v%2])continue;
			vis[t.y][t.v%2]=1;
			for(N i:e[t.y]){
				ll tt;
				if(i.v<=t.v+1)tt=t.v+1;
				else{
					tt=i.v;
					if(tt%2==t.v%2)tt++;
				}
				if(dis[i.y][tt%2]>tt){
					dis[i.y][tt%2]=tt;
					q.push({i.y,tt});
				}
			}
		}
		ll ans=1e18;
		for(int j=0;j<2;j++){
			ll mx=0;
			for(int i=1;i<=n;i++){
				if(dis[i][j]>mx)mx=dis[i][j];
			}
			if(mx!=0x3f3f3f3f3f3f3f3f)ans=min(ans,mx);
		}
		if(ans==1e18)cout<<"-1\n";
		else cout<<ans*o<<'\n';
	}
	return 0;
}