#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;

struct node{int x,y,k,next,other;};
node q[2110005];
int len,last[10005];
int n,m,st,ed,maxx;
int a[500][500],sc[500],sa[500];

void ins(int x,int y,int k)
{
	len++;
	q[len].x=x;q[len].y=y;q[len].k=k;
	q[len].next=last[x];last[x]=len;
	
	len++;
	q[len].x=y;q[len].y=x;q[len].k=0;
	q[len].next=last[y];last[y]=len;
	
	q[len-1].other=len;
	q[len].other=len-1;
}

int list[10005],head,tail,h[10005];

bool build()
{
	memset(h,0,sizeof(h));
	list[1]=st;h[st]=1;head=1;tail=2;
	while(head!=tail)
	{
		int x=list[head];
		for(int i=last[x];i;i=q[i].next)
		{
			int y=q[i].y;
			if(q[i].k>0 && h[y]==0)
			{
				h[y]=h[x]+1;
				list[tail]=y;
				tail++;
			}
		}
		head++;
	}
	if(h[ed]>0)	return true;
	return false;
}

int find(int x,int f)
{
	if(x==ed)	return f;
	int s=0,t;
	for(int i=last[x];i;i=q[i].next)
	{
		int y=q[i].y;
		if(q[i].k>0 && h[y]==(h[x]+1) && s<f)
		{
			t=find(y,min(q[i].k,f-s));
			s+=t;q[i].k-=t;q[q[i].other].k+=t;
		}
	}
	if(s==0)	h[x]=0;
	return s;
}

int check(int x)
{
	len=0;
	st=n+1;ed=st+1;
	memset(last,0,sizeof(last));
	for(int i=1;i<=n;i++)
	{
		ins(st,i,sc[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j && a[i][j]<=x)
			{
			//	printf("%d %d %d\n",i,j+n,a[i][j]);
				ins(i,j,999999999);
			}	
		}
	}	
	for(int i=1;i<=n;i++)
	{
		ins(i,ed,sa[i]);
	}
	int s=0;
	while(build())
	{
		s+=find(st,999999999);
	}
	return s;
}

int main()
{
	while(1)
	{
		scanf("%d",&n);
		if(n==0)	return 0;
		maxx=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&sc[i]);
			maxx+=sc[i];
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&sa[i]);
		}
		scanf("%d",&m);
		int x,y,k;
		memset(a,63,sizeof(a));
		int da=-1;
		for(int i=1;i<=m;i++)
		{
			scanf("%d %d %d",&x,&y,&k);
			a[x][y]=a[y][x]=k;
			da=max(da,k);
		}
		for(int k=1;k<=n;k++)
		{
			a[k][k]=0;
			for(int i=1;i<=n;i++)
			{
				if(i!=k)
				{
					for(int j=1;j<=n;j++)
					{
						if(j!=i && j!=k)
						{
							if(a[i][j]>a[i][k]+a[k][j])
							{
								a[i][j]=a[i][k]+a[k][j];
							}
						}
					}
				}
			}
		}
		int ans=-1,l=0,r=da+5,mid;
		while(l<=r)
		{
			mid=(l+r)/2;
			if(check(mid)>=maxx)
			{
				r=mid-1;
				ans=mid;
			}
			else
			{
				l=mid+1;
			}
		}
		if(ans!=-1)	printf("%d\n",ans);
		else	printf("No Solution\n");
	}
}