#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;

#define pb push_back
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

pii dfs(int n, int m, int w, int sp) { // {min(all), min(sp is selected)}
    vector<int> V;
    vector<pii> E;
    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        V.eb(u); V.eb(v); E.eb(u, v);
    }
    sort(all(V));
    V.erase(unique(all(V)), V.end());
    auto getpos = [&](int w) {
        return lower_bound(all(V), w) - V.begin();
    };
    vector<tii> child;
    rep(i, 1, w) {
        int u, v, nn, mm, ww;
        cin >> u >> v >> nn >> mm >> ww;
        auto [fc, gc] = dfs(nn, mm, ww, v);
        child.eb(getpos(u), fc, gc);
    }

    if (sp != -1) sp = getpos(sp);
    int f = INT_MAX, g = INT_MAX;
    auto ok = [&](int S) {
        for (auto [u, v] : E) {
            u = getpos(u); v = getpos(v);
            if (!((S >> u) & 1) && !((S >> v) & 1)) return false;
        }
        return true;
    };
    rep(S, 0, (1 << V.size()) - 1) if (ok(S)) {
        int cst = __builtin_popcount(S);
        for (auto [u, fc, gc] : child) {
            cst += (((S >> u) & 1) ? fc : gc);
        }
        f = min(f, cst);
        if (sp != -1 && ((S >> sp) & 1)) g = min(g, cst);
    }
    return {f, g};
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, w;
    while (cin >> n >> m >> w) printf("%d\n", dfs(n, m, w, -1).first);
    return 0;
}