#include <stdio.h>

#define MAX_N 151
#define MAX_T 3501
#define MAX_P 8001

struct nod{
	int info;
	int key;
	nod *urm;
}*v[MAX_N];

int n,m,p,k,A[MAX_T][MAX_N],w[MAX_P][2],tmax;

void adauga(int a,int b,int c){
	nod *p;
	p=new nod;
	p->info=c;
	p->key=b;
	p->urm=v[a];
	v[a]=p;
}
	
void citire(){
	int i,a,b,c;
	FILE *fin=fopen("amenzi.in","r");
	fscanf(fin,"%d %d %d %d",&n,&m,&k,&p);
	for (i=1;i<=m;i++){
		fscanf(fin,"%d %d %d",&a,&b,&c);
		adauga(a,b,c);
		adauga(b,a,c);
	}
	for (i=1;i<=k;i++){
		fscanf(fin,"%d %d %d",&a,&b,&c);
		A[b][a]+=c;
		if (tmax<b)
			tmax=b;
	}
	for (i=1;i<=p;i++){
		fscanf(fin,"%d %d",&w[i][0],&w[i][1]);
		if (w[i][1]>tmax)
			tmax=w[i][1];
	}
	fclose(fin);
}

void pd(){
	nod *p;
	int i,j,max;
	
	for (j=2;j<=n;j++)
		A[0][j]=-1;
	for (i=1;i<=tmax;i++)
		for (j=1;j<=n;j++){
			max=-1;
			for (p=v[j];p!=NULL;p=p->urm)
				if (i-(p->info)>=0)
					if (A[i-(p->info)][p->key]>max)
						max=A[i-(p->info)][p->key];
			if (i-1>=0)
				if (max<A[i-1][j])
					max=A[i-1][j];
			if (max!=-1)
				A[i][j]+=max;
			else
				A[i][j]=-1;
		}
}

void afisare(){
	FILE *fout=fopen("amenzi.out","w");
	for (int i=1;i<=p;i++){
		fprintf(fout,"%d\n",A[w[i][1]][w[i][0]]);
	}
	fclose(fout);
}

int main(){
	citire();
	pd();
	afisare();
	printf("%d\n",tmax);
	for (int i=0;i<=tmax;i++){
		for (int j=1;j<=n;j++)
			printf("%d ",A[i][j]);
		printf("\n");
	}
	return 0;
}