TOI15: Budget

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

typedef long long lli;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N = 3000;

vector<tiii> edges(0);
vector<pii> promo(0);
int ds[N + 10];
int nVertex, nEdge, nPromo;

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    return ds[u] = dsFind(ds[u]);
}

void dsUnion(int u, int v){
    ds[dsFind(u)] = dsFind(v);
}

int main(){

    scanf("%d %d", &nVertex, &nEdge);
    for(int i = 0; i < nVertex; ++i){
        ds[i] = i;
    }
    for(int i = 1; i <= nEdge; ++i){
        int u, v, w, roof;
        scanf("%d %d %d %d", &u, &v, &w, &roof);
        if(roof == 1){
            dsUnion(u, v);
        } else {
            edges.emplace_back(w, u, v);
        }
    }
    sort(edges.begin(), edges.end());

    scanf("%d", &nPromo);
    for(int i = 1; i <= nPromo; ++i){
        int dist, cost;
        scanf("%d %d", &dist, &cost);
        promo.emplace_back(dist, cost);
    }
    sort(promo.begin(), promo.end());
    int currMn = 1e9;
    for(int i = nPromo - 1; i >= 0; --i){
        if(promo[i].second < currMn){
            currMn = promo[i].second;
        }
        promo[i].second = currMn;
    }

    lli sum = 0;
    for(tiii e : edges){
        int w = get<0>(e);
        int u = get<1>(e);
        int v = get<2>(e);
        int x = dsFind(u);
        int y = dsFind(v);
        if(x != y){
            ds[x] = y;
            sum += promo[lower_bound(promo.begin(), promo.end(), make_pair(w, 0)) - promo.begin()].second;
        }
    }

    cout << sum;

    return 0;
}