#include"iostream"#include"cstdio"#include"cstring"#include"cmath"#include"algorithm"#include"cstdlib"#include"queue"using namespace std;#define LL intconst int inf=1<<30;const int maxn=605;const int maxm=maxn*maxn;struct edge{ int u,v; LL c,f; int next;};int eh[maxn],tot;edge et[maxm];void add(int u,int v,LL c,LL f){ edge E={u,v,c,f,eh[u]}; et[tot]=E,eh[u]=tot++;}void addedge(int u,int v,LL c){ add(u,v,c,0),add(v,u,0,0);}int cur[maxn],cnt[maxn],dis[maxn],pre[maxn];LL low[maxn];void rebfs(int s,int t,int n){ for(int i=0;i<=n;i++) { cnt[i]=0; dis[i]=n; } queue<int>q; dis[t]=0; cnt[0]=1; q.push(t); while(!q.empty()) { int u=q.front(); q.pop(); for(int now=eh[u];now!=-1;now=et[now].next) { if(et[now^1].c==0||dis[et[now].v]<n)continue; dis[et[now].v]=dis[u]+1; cnt[dis[et[now].v]]++; q.push(et[now].v); } }}LL isap(int s,int t,int n){ rebfs(s,t,n); int u,v,now,i; for(i=0;i<=n;i++) { low[i]=0; } for(u=0;u<=n;u++) cur[u]=eh[u]; LL flow=0; u=s; low[s]=inf; cnt[0]=n; while(dis[s]<n) { for(now=cur[u];now!=-1;now=et[now].next) if(et[now].c-et[now].f>0&&dis[u]==dis[v=et[now].v]+1)break; if(now!=-1) { cur[u]=now; pre[v]=now; low[v]=et[now].c-et[now].f; low[v]=low[v]<low[u] ? low[v]:low[u]; u=v; if(u==t) { for(;u!=s;u=et[pre[u]].u) {et[pre[u]].f+=low[t]; et[pre[u]^1].f-=low[t]; } flow+=low[t];low[s]=inf; } } else { if(--cnt[dis[u]]==0)break; dis[u]=n; cur[u]=eh[u]; for(now=eh[u];now!=-1;now=et[now].next) if(et[now].c-et[now].f>0&&dis[u]>dis[et[now].v]+1) dis[u]=dis[et[now].v]+1; cnt[dis[u]]++; if(u!=s)u=et[pre[u]].u; } } return flow;}void init(){ tot=0; memset(eh,-1,sizeof(eh));}int gd[206],ho[209];int map[206][206];int mat[206][206];int dist[maxm];void floyd(int n,int d){int i,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(map[i][j]<=d)mat[i][j]=map[i][j];elsemat[i][j]=inf;for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(mat[i][k]!=inf&&mat[k][j]!=inf)if(mat[i][k]+mat[k][j]<mat[i][j])mat[i][j]=mat[i][k]+mat[k][j];}int main(){int n;while(~scanf("%d",&n)){if(n==0)break;int i,j,k;int sum=0;for(i=1;i<=n;i++){scanf("%d",&gd[i]);sum+=gd[i];}for(i=1;i<=n;i++)scanf("%d",&ho[i]);int m;scanf("%d",&m);for(i=0;i<=n;i++)for(j=0;j<=n;j++){if(i==j)map[i][j]=0;elsemap[i][j]=inf;}for(i=0;i<m;i++){int a,b,d;scanf("%d%d%d",&a,&b,&d);map[a][b]=d;map[b][a]=d;dist[i]=d;}sort(dist,dist+m);int l=0;int r=m-1;int s=0;int t=n+n+1;int ans=-1;while(l<=r){init();int mid=(l+r)>>1;floyd(n,dist[mid]);for(i=1;i<=n;i++){addedge(s,i,gd[i]);addedge(i+n,t,ho[i]);}for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(mat[i][j]<inf)addedge(i,j+n,inf);}int w=isap(s,t,t-s+1);if(w==sum){ans=dist[mid];r=mid-1;}else{l=mid+1;}}if(ans>0)printf("%dn",ans);elseprintf("No Solutionn");}return 0;}
