/*

Author: fffasttime

Date: 

*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define inc(i,n) for (int i=0;i<n;i++)

const int N=100010;

struct Node{

	int x,y,c;

	bool operator<(const Node &v) const{return c>v.c;}

}e[100010];

int pa[20010];

int fi(int x){if (pa[x]!=x) pa[x]=fi(pa[x]); return pa[x];}

int main(){

	int T; cin>>T;

	while (T--){

		int n,m,K,x,ec=0;

		cin>>m>>n>>K>>x;

		for (int i=0;i<x;i++){

			int x,y,c; scanf("%d%d%d",&x,&y,&c);

			e[ec++]=(Node){x,y+m,c};

		}

		inc(i,n+m) pa[i]=i;

		sort(e,e+ec);

		int sum=0;

		for (int i=0,k=0;i<n+m-1 && k<ec;i++){

			while (fi(e[k].x)==fi(e[k].y) && k<ec) k++;

			if (k>=ec) break;

			pa[pa[e[k].x]]=pa[e[k].y];

			sum+=e[k].c;

		}

		cout<<(n+m)*K-sum<<'\n';

	}

	return 0;

}