// Program written by EricWu ~~~
#include <bits/stdc++.h>
 
#define lowbit(x) (x & -x)
 
using namespace std;
 
inline char gc(void) {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
 
#define gc() getchar()
 
template <class T> inline void read(T &x) {
    T f = 1; x = 0; static char c = gc();
    for (; !isdigit(c); c = gc()) if (c == '-') f = -f;
    for (; isdigit(c); c = gc()) x = x * 10 + (c & 15);
    if (f == -1) x = -x;
}
 
inline void readstr(char *s) {
    do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
    do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
    *s = 0; return;
}
 
inline void readch(char&x) { while (isspace(x = gc())); }
 
char pf[100000], *o1 = pf, *o2 = pf + 100000;
#define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
template <class T>
inline void println(T x, char c = '\n') {
    if (x < 0) ot(45), x = -x;
    static char s[15], *b; b = s;
    if (!x) *b ++= 48;
    for (; x; * b ++= x % 10 + 48, x /= 10);
    for (; b-- != s; ot(*b)); ot(c);
}
 
template <class T> inline void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
 
template <class T> inline void writeln(T x, char c = '\n') { write(x); putchar(c); }
template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
 
#define Ms(arr, opt) memset(arr, opt, sizeof(arr))
#define Mp(x, y) make_pair(x, y)
#define endl '\n'

typedef long long ll;
typedef pair <int, int> pii;
typedef array<int, 3> piii;
using i64 = long long;
const int inf = 1e9;

void solve() {
    int n, m1, m2; read(n), read(m1), read(m2);
    vector rules1(m1, vector<int>(3, 0));
    vector rules2(m2, vector<int>(3, 0));
    for (int i = 0;i < m1;i++) 
        read(rules1[i][0]), read(rules1[i][1]), read(rules1[i][2]);
    for (int i = 0;i < m2;i++) 
        read(rules2[i][0]), read(rules2[i][1]), read(rules2[i][2]);
    int l = 0, r = n, ans = n;
    vector adj(n + 2, vector<pair<int, int>>());
    for (int i = 1;i <= n;i++) {
        adj[i].emplace_back(i - 1, 0);
        adj[i - 1].emplace_back(i, 1);
    }
    for (int i = 0;i < m1;i++) {
        adj[rules1[i][1]].emplace_back(rules1[i][0] - 1, -rules1[i][2]);
    }
    int S = n + 1;
    for (int i = 0;i <= n;i++) adj[S].emplace_back(i, 0);
    auto check = [&](int mid) -> bool {
        for (int i = 0;i < m2;i++) {
            adj[rules2[i][0] - 1].emplace_back(rules2[i][1], mid - rules2[i][2]);
        }
        adj[0].emplace_back(n, mid); adj[n].emplace_back(0, -mid);
        vector<int> dis(n + 2, inf), cnt(n + 2, 0);
        vector<bool> vis(n + 2, false);
        queue<int> q; q.emplace(S), vis[S] = 1, dis[S] = 0;
        while (q.size()) {
            auto u = q.front(); q.pop();
            vis[u] = 0;
            for (auto &[v, w] : adj[u]) {
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    if (!vis[v]) {
                        q.emplace(v);
                        vis[v] = true;
                        cnt[v] ++;
                        if (cnt[v] >= n + 1) return false;
                    }
                }
            }
        }
        
        return true;
    };
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            for (int i = 0;i < m2;i++) {
                adj[rules2[i][0] - 1].pop_back();
            }
            adj[0].pop_back(); adj[n].pop_back();
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    writeln(ans);
}

int main() {
    int T = 1; read(T);
    while (T--) solve();
    // system("pause");
    return 0;
}