#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
typedef unsigned long long ull;
const int maxN = 65;
ull m[2 * maxN];
ll p[2 * maxN];
vector<int> g[maxN];
bool good[2 * maxN];
ull D[64];
const ull one = 1;
bool add(ull p) {
    for (int i = 63; i >= 0; i--) {
        p = min(p, (p ^ D[i]));
    }
    if (p == 0) return false;
    for (int i = 63; i >= 0; i--) {
        if (p & (one << i)) {
            D[i] = p;
            break;
        }
    }
    return true;
}
bool check(int v) {
    memset(D, 0, sizeof D);
    bool ok = true;
    if (good[2 * v]) ok &= add(m[2 * v]);
    if (good[2 * v + 1]) ok &= add(m[2 * v + 1]);
    for (int t : g[v]) {
        if (good[2 * t]) ok &= add(m[2 * t]);
        if (good[2 * t + 1]) ok &= add(m[2 * t + 1]);
        if (!ok) return false;
    }
    return ok;
}
pair<ll,ll> dst[2 * maxN];
int prv[2 * maxN];
void solve() {
    memset(good, 0, sizeof good);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> m[2 * i + j] >> p[2 * i + j];
        }
    }
    for (int i = 0; i < n; i++) {
        g[i].clear();
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    int START = 2 * n;
    int FIN = 2 * n + 1;
    for (int it = 0; it < n; it++) {
        vector<tuple<int,int,ll>> edges;
        for (int x = 0; x < 2 * n; x++) {
            for (int y = 0; y < 2 * n; y++) {
                if (good[x] && !good[y]) {
                    //XOR matroid
                    good[x] ^= 1;
                    good[y] ^= 1;
                    bool OK = true;
                    OK &= check(x >> 1);
                    OK &= check(y >> 1);
                    if (OK) {
                        for (int p : g[x >> 1]) {
                            OK &= check(p);
                            if (!OK) break;
                        }
                        if (OK) {
                            for (int p : g[y >> 1]) {
                                OK &= check(p);
                                if (!OK) break;
                            }
                        }
                    }
                    if (OK) {
                        edges.emplace_back(x, y, +p[x]);
                    }
                    good[x] ^= 1;
                    good[y] ^= 1;
                    if (!good[y ^ 1] || ((x >> 1) == (y >> 1))) {
                        edges.emplace_back(y, x, -p[y]);
                    }
                }
            }
        }
        for (int x = 0; x < 2 * n; x++) {
            if (!good[x]) {
                if (!good[x ^ 1]) {
                    edges.emplace_back(x, FIN, -p[x]);
                }
                good[x] ^= 1;
                bool OK = check(x >> 1);
                if (OK) {
                    for (int p : g[x >> 1]) {
                        OK &= check(p);
                        if (!OK) break;
                    }
                }
                if (OK) {
                    edges.emplace_back(START, x, 0);
                }
                good[x] ^= 1;
            }
        }
        for (int i = 0; i <= FIN; i++) {
            dst[i] = {1e18, -1};
        }
        dst[START] = {0, 0};
        memset(prv, -1, sizeof prv);
        for (int i = 0; i <= 2 * n + 5; i++) {
            for (auto it : edges) {
                ll w = get<2>(it);
                int u = get<0>(it);
                int v = get<1>(it);
                auto upd = make_pair(dst[u].first + w, dst[u].second + 1);
                if (dst[v] > upd) {
                    dst[v] = upd;
                    prv[v] = u;
                }
            }
        }
        if (dst[FIN].first > 1e17) {
            cout << -1 << '\n';
            return;
        }
        int c = prv[FIN];
        while (c != START) {
            good[c] ^= 1;
            c = prv[c];
        }
    }
    ll cost = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (good[i]) cost += p[i];
    }
    cout << cost << '\n';

}



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst = 1;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}