#include<bits/stdc++.h>
using namespace std;
const int N=2.5e4+50;
const int inf=1e9+7+2*N;
int c,T;
int n,m,o;
vector<pair<int,int>> G[N];
int dis[N][2];
int vis[N][2];
inline void dijkstra(){
	for(int i=1;i<=n;i++) dis[i][0]=dis[i][1]=inf,vis[i][0]=vis[i][1]=0;
	dis[1][0]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0,1});
	while(pq.size()){
		int p=pq.top().second;
		int d=pq.top().first;
		pq.pop();
		if(vis[p][d%2]) continue;
		vis[p][d%2]=1;
		for(auto j:G[p]){
			int u=j.first,w=j.second;
			if(max(dis[p][0]+1,w/2*2+1)<dis[u][1]){
				dis[u][1]=max(dis[p][0]+1,w/2*2+1);
				pq.push({dis[u][1],u});
			}
			if(max(dis[p][1]+1,(w+1)/2*2)<dis[u][0]){
				dis[u][0]=max(dis[p][1]+1,(w+1)/2*2);
				pq.push({dis[u][0],u});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>c>>T;
	while(T--){
		cin>>n>>m>>o;
		for(int i=1;i<=n;i++) G[i].clear();
		bool flag=1;
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			G[u].push_back({v,w});
			G[v].push_back({u,w});
			if((u==1 || v==1) && w==1) flag=0;
		}
		if(flag){//特判
			cout<<"-1\n";
			continue;
		}
		dijkstra();
		int ans1=0,ans2=0;
		for(int i=1;i<=n;i++){
			ans1=max(ans1,dis[i][0]);
			ans2=max(ans2,dis[i][1]);
		}
		if(ans1>=inf && ans2>=inf) cout<<"-1\n";
		else cout<<min(ans1,ans2)*o<<'\n';
	}
}