Budget

/*
    Task    : Budget
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 12 December 2022 [20:00]
*/
#include<bits/stdc++.h>
using namespace std;
struct A{
    int u,v,w,st;
    bool operator < (const A&o) const{
        return w<o.w;
    }
};
vector<A > edges;
int p[3010];
pair<int ,int > allPackages[300010];
int findRoot(int now){
    if(now == p[now])   return now;
    else                return p[now] = findRoot(p[now]);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int b,e,s,t,l,r;
    cin >> b >> e;
    for(int i=0;i<b;i++)
        p[i] = i;
    for(int i=1;i<=e;i++){
        cin >> s >> t >> l >> r;
        edges.push_back({s,t,l,r});
        if(r == 1){
            int rs = findRoot(s);
            int rt = findRoot(t);
            p[rs] = rt;
        }
    }
    int pack;
    cin >> pack;
    for(int i=1;i<=pack;i++)
        cin >> allPackages[i].first >> allPackages[i].second;
    sort(allPackages+1,allPackages+pack+1);
    for(int i=pack-1;i>=1;i--)
        allPackages[i].second = min(allPackages[i].second,allPackages[i+1].second);
    for(int i=0;i<e;i++){
        int idx = lower_bound(allPackages+1,allPackages+pack+1,make_pair(edges[i].w,0))-allPackages;
        edges[i].w = allPackages[idx].second;
    }
    sort(edges.begin(),edges.end());
    long long ans = 0;
    for(int i=0;i<e;i++){
        int ru = findRoot(edges[i].u);
        int rv = findRoot(edges[i].v);
        if(ru == rv)    continue;
        ans+=edges[i].w;
        p[ru] = rv;
    }
    cout << ans << '\n';
    return 0;
}