#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int row,line,keyn,haha,r;

struct typekey{

	int x,y;

}key[15][20]={0};

struct node{

	int to;

	int nxt;

	int w;

}a[1000000]={0};

int num[1000][1000],fg[1000][1000],kn[15];

int layer,n,m,tot;

int head[1000000];

void add(int x,int y,int w)

{

	tot++;

	a[tot].to=y;

	a[tot].w=w;

	a[tot].nxt=head[x];

	head[x]=tot;

}

int dis[1000000],vis[1000000],q[1000000],inf=99999999;

void spfa()

{

	int i,j,k,hea,tail;

	for(i=1;i<=n;i++) dis[i]=inf;

	dis[1]=0;

	vis[1]=1;

	hea=tail=1;

	q[1]=1;

	while(hea<=tail)

	{

		i=q[hea];

		for(k=head[i];k;k=a[k].nxt)

		{

			j=a[k].to;

			if(dis[j]>dis[i]+a[k].w)

			{

				dis[j]=dis[i]+a[k].w;

				if(!vis[j])

				{

					q[++tail]=j;

					vis[j]=1;

				}

			}

		}

		vis[i]=0;

		hea++;

	}

}

void build()

{

	int i,j,k,x,y,t;

	bool havekey[15]={0};

	m=row*line;

	layer=1<<keyn;

	n=m*layer;

	for(k=0;k<layer;k++)

	{

		for(i=1;i<=keyn;i++)

		{

			if(k&(1<<(i-1))) havekey[i]=1;

			else havekey[i]=0;

		}

		for(i=1;i<=row;i++)

		{

			for(j=1;j<=line;j++)

			{

				x=num[i][j];

				y=num[i][j+1];

				if(y!=0&&fg[x][y]!=-1)

				{

					if(fg[x][y]==0||havekey[fg[x][y]])

					{

						add(k*m+x,k*m+y,1);

						add(k*m+y,k*m+x,1);

						//cout<<k*m+x<<" "<<k*m+y<<" "<<k*m+y<<" "<<k*m+x<<endl;

					}

				}

				y=num[i+1][j];

				if(y!=0&&fg[x][y]!=-1)

				{

					if(fg[x][y]==0||havekey[fg[x][y]])

					{

						add(k*m+x,k*m+y,1);

						add(k*m+y,k*m+x,1);

						//cout<<k*m+x<<" "<<k*m+y<<" "<<k*m+y<<" "<<k*m+x<<endl;

					}

				}

			}

		}

		for(i=1;i<=keyn;i++)

		{

			if(!havekey[i])

			{

				t=k+(1<<(i-1));

				for(j=1;j<=kn[i];j++)

				{

					x=num[key[i][j].x][key[i][j].y];

					add(k*m+x,t*m+x,0);

					//cout<<k*m+x<<" "<<t*m+y<<endl;

				}

			}

		}

	}

}

void read()

{

	int i,j,k,x,y,p;

	cin>>row>>line>>keyn>>haha;

	k=0;

	for(int i=1;i<=row;i++)

	{

		for(int j=1;j<=line;j++)

		{

			num[i][j]=++k;

		}

	}

	cin>>r;

	for(int i=1;i<=r;i++)

	{

		scanf("%d%d",&x,&y);j=num[x][y];

		scanf("%d%d",&x,&y);k=num[x][y];

		scanf("%d",&p);

		if(p==0) p=-1;

		fg[j][k]=fg[k][j]=p;

	}

	scanf("%d",&r);

	for(int i=1;i<=r;i++)

	{

		scanf("%d%d%d",&x,&y,&p);

		kn[p]++;

		key[p][kn[p]].x=x;

		key[p][kn[p]].y=y;

	}

}

int main()

{

	memset(fg,0,sizeof(fg));

	read();

	build();

	spfa();

	int ans=inf;

	for(int i=0;i<layer;i++)

	{

		ans=min(ans,dis[i*m+num[row][line]]);

	}

	if(ans!=inf)

	{

		if(ans<=haha) cout<<ans<<endl;

		else cout<<(ans-haha)*2+haha;

	}

	else cout<<char(92)<<" Oh,no! Tita will die /";

}