#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef double ld;
namespace simplex
{
const int N=107,M=307;
const ld eps=1e-5;
inline int sgn(ld x){return (-eps<=x&&x<=eps)?0:(x>0?1:-1);}
int n,m;ld a[M][N],b[M][N];int id[N+M];
void pivot(int e,int l)
{
//	printf(" pivot %d %d\n",e,l);
	std::swap(id[n+l],id[e]);
	ld kk=-a[l][e];a[l][e]=-1;
	for(int j=0;j<=n;++j)a[l][j]/=kk;
	for(int i=0;i<=m;++i)if(i!=l&&sgn(a[i][e]))
	{
		ld coef=a[i][e];a[i][e]=0;
		for(int k=0;k<=n;++k)a[i][k]+=coef*a[l][k];
	}
}
ld simplex(int _n,int _m)
{
//	puts("simplex");
	n=_n;m=_m;memcpy(a+1,b+1,m*sizeof*b);
	for(int i=1;i<=n+m;++i)id[i]=i;
	while(1)
	{
		int e=0,l=0;
		for(int i=1;i<=m;++i)if(sgn(a[i][0])<0&&(!l||a[i][0]<a[l][0]))l=i;
		if(!l)break;for(int i=1;i<=n;++i)if(sgn(a[l][i])>0&&id[i]>id[e])e=i;
		pivot(e,l);
	}
	while(1)
	{
		int e=0,l=0;
		for(int i=1;i<=n;++i)if(sgn(a[0][i])>0&&(!e||a[0][e]<a[0][i]))e=i;
		if(!e)return **a;
		for(int i=1;i<=m;++i)
			if(sgn(a[i][e])<0)
			{
				if(!l){l=i;continue;}
				ld crs=a[l][0]*a[i][e]-a[i][0]*a[l][e];
				if(sgn(crs)<0||(!sgn(crs)&&id[i]>id[l]))l=i;
			}
		pivot(e,l);
	}
}
}
const int N=37,M=107;
struct pii{int v,w;};bool vis[N];int d[N][N];
bool operator<(pii x,pii y){return x.w>y.w;}
void dijkstra(int s,int n,int*dis,int*pre)
{
	memset(dis,0x3f,N<<2);memset(vis,0,N);
	dis[s]=pre[s]=0;//printf("s=%d\n",s);
	while(1)
	{
	    int p=0;for(int i=1;i<=n;++i)if(!vis[i]&&(!p||dis[i]<dis[p]))p=i;
	    if(!p)return;vis[p]=1;for(int j=1;j<=n;++j)if(dis[j]>dis[p]+d[p][j])dis[j]=dis[p]+d[p][j],pre[j]=p;//,printf("pr[%d]=%d\n",j,pre[j]);
	}
}
int id[N][N],pre[N][N],dis[N][N];
int ds[M];
int main()
{
//	freopen("39-random20.in","r",stdin);
	int n,m=0;scanf("%d",&n);
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
	{
		scanf("%d",d[i]+j);
		if(i!=j&&d[i][j]!=-1)ds[id[i][j]=++m]=d[i][j];
		else if(d[i][j]==-1)d[i][j]=0x3f3f3f3f;
	}
	for(int i=1;i<=n;++i)dijkstra(i,n,dis[i],pre[i]);
	for(int i=1;i<=m;++i)
	{
		simplex::b[i][0]=ds[i];
		simplex::b[i][i]=-1;
	}
	int ma,mb;scanf("%d",&ma);
	for(int i=1;i<=ma;++i)
	{
		int s,t,d;scanf("%d%d%d",&s,&t,&d);
		++s;++t;d-=dis[s][t];
		simplex::b[m+i+i-1][0]=d;
		simplex::b[m+i+i][0]=-d;
		for(int j=t;j!=s;j=pre[s][j])
		{
			int p=pre[s][j],ii=id[p][j];
//			printf("p=%d ii=%d\n",p,ii);
			simplex::b[m+i+i-1][ii]=-1;
			simplex::b[m+i+i][ii]=1;
		}
	}
	scanf("%d",&mb);
	for(int i=1;i<=mb;++i)
	{
		int s,t;scanf("%d%d",&s,&t);++s;++t;
		for(int j=0;j<=m;++j)simplex::a[0][j]=0;
		for(int j=t;j!=s;j=pre[s][j])
		{
			int p=pre[s][j],ii=id[p][j];
			simplex::a[0][ii]=-1;
		}
		ld mn=-simplex::simplex(m,m+ma*2)+dis[s][t];
		for(int j=0;j<=m;++j)simplex::a[0][j]=0;
		for(int j=t;j!=s;j=pre[s][j])
		{
			int p=pre[s][j],ii=id[p][j];
			simplex::a[0][ii]=1;
		}
		ld mx=simplex::simplex(m,m+ma*2)+dis[s][t];
		printf("%d %d %.8lf %.8lf\n",s-1,t-1,mn,mx);
	}
	return 0;
}