#include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef long double ld;

 typedef pair<int,int> PII;

 typedef pair<ll,ll> Pll;

 typedef vector<int> VI;

 typedef vector<PII> VII;

 typedef pair<ll,ll>P;

 #define N  500010

 #define M  1000000

 #define INF 1e9

 #define fi first

 #define se second

 #define MP make_pair

 #define pb push_back

 #define pi acos(-1)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)

 #define lowbit(x) x&(-x)

 #define Rand (rand()*(1<<16)+rand())

 #define id(x) ((x)<=B?(x):m-n/(x)+1)

 #define ls p<<1

 #define rs p<<1|1

 #define fors(i) for(auto i:e[x]) if(i!=p)

 const int MOD=1e9+,inv2=(MOD+)/;

       double eps=1e-;

       int dx[]={-,,,};

       int dy[]={,,-,};

 struct edge

 {

     int x,y,z;

 }a[N],b[N];

 int head[N],vet[N],nxt[N],inq[N],dis[N],stk[N],len[N],t[N],

     n,m1,m2,tot;

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 ll readll()

 {

    ll v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 void add(int a,int b,int c)

 {

     nxt[++tot]=head[a];

     vet[tot]=b;

     len[tot]=c;

     head[a]=tot;

 }

 void build(int k)

 {

     //printf("k=%d\n",k);

     tot=;

     rep(i,,n) head[i]=;

     rep(i,,n-)

     {

         add(i+,i,);

         add(i,i+,);

     }

     rep(i,,m1) add(a[i].y,a[i].x-,-a[i].z);

     rep(i,,m2) add(b[i].x-,b[i].y,k-b[i].z);

     add(,n,k);

     add(n,,-k);

 }

 int isok()

 {

     rep(i,,n) inq[i]=dis[i]=t[i]=;

     int top=;

     rep(i,,n)

     {

         top++;

         stk[top]=i;

         inq[i]=;

         t[]=i;

     }

     while(top)

     {

         int u=stk[top];

         top--;

         inq[u]=;

         int e=head[u];

         while(e)

         {

             int v=vet[e];

             if(dis[u]+len[e]<dis[v])

             {

                 dis[v]=dis[u]+len[e];

                 if(!inq[v])

                 {

                     top++;

                     stk[top]=v;

                     inq[v]=;

                     t[v]++;

                     if(t[v]==n+) return ;

                 }

             }

             e=nxt[e];

         }

     }

     return ;

 }

 void solve()

 {

     n=read(),m1=read(),m2=read();

     rep(i,,m1) a[i].x=read(),a[i].y=read(),a[i].z=read();

     rep(i,,m2) b[i].x=read(),b[i].y=read(),b[i].z=read();

     int l=,r=n,last=n;

     while(l<=r)

     {

         int mid=(l+r)>>;

         build(mid);

         if(isok()){last=mid; r=mid-;}

          else l=mid+;

     }

     printf("%d\n",last);

 }

 int main()

 {

     //freopen("1.in","r",stdin);

     int cas=read();

     while(cas--) solve();

     return ;

 }