Budget

/*
    Task    : _example
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 23 November 2022 [21:21]
*/
#include<bits/stdc++.h>
using namespace std;
struct A{
    int u,v,w;
    bool operator < (const A&o) const{
        return w > o.w;
    }
};
priority_queue<A > heap;
vector<A > g;
vector<pair<int ,int > > pack;
int p[3010],a[500010];
int findroot(int u){
    if(p[u] == u)   return u;
    else            return p[u] = findroot(p[u]);
}
int main(){
    int n,m,u,v,w,state,ru,rv,k;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
        p[i] = i;
    while(m--){
        scanf("%d %d %d %d",&u,&v,&w,&state);
        if(state == 1){
            ru = findroot(u);
            rv = findroot(v);
            p[ru] = rv;
        }else{
            g.push_back({u,v,w});
        }
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        scanf("%d %d",&u,&v);
        pack.push_back({u,v});
    }
    sort(pack.begin(),pack.end());
    a[k] = pack.back().first;
    for(int i=pack.size()-2;i>=0;i--){
        pack[i].second = min(pack[i].second,pack[i+1].second);
        a[i] = pack[i].first;
    }
    for(auto x:g){
        w = lower_bound(a,a+k,x.w)-a;
        heap.push({x.u,x.v,pack[w].second});
    }
    long long ans = 0;
    while(!heap.empty()){
        auto now = heap.top();
        heap.pop();
        ru = findroot(now.u);
        rv = findroot(now.v);
        if(ru == rv)    continue;
        ans+=now.w;
        p[ru] = rv;
    }
    printf("%lld\n",ans);
    return 0;
}