Q2v2

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    lli a, n, m;
    cin >> a >> n >> m;

    vector<tuple<string, string, lli>> quotations;
    unordered_map<string, unordered_map<string, lli>> direct;

    for(lli i = 0; i < n; i++)
    {
        string s1, s2;
        lli w;
        cin >> s1 >> s2 >> w;
        quotations.emplace_back(s1, s2, w);
        if(direct[s1].find(s2) == direct[s1].end())
        {
            direct[s1][s2] = w;
        }
        else
        {
            direct[s1][s2] = min(direct[s1][s2], w);
        }
    }

    for(lli i = 0; i < m; ++i)
    {
        string s1, s2;
        lli w;
        cin >> s1 >> s2 >> w;
        if(direct[s1].find(s2) == direct[s1].end())
        {
            direct[s1][s2] = w;
        }
        else
        {
            direct[s1][s2] = min(direct[s1][s2], w);
        }
    }

    lli ans = 0;
    for(auto &quote : quotations)
    {
        string s1 = get<0>(quote);
        string s2 = get<1>(quote);
        lli price = get<2>(quote);

        lli minimal_price = 1e10;

        if(direct[s1].count(s2))
        {
            minimal_price = direct[s1][s2];
        }

        if(direct.count(s1))
        {
            for(auto &x_entry : direct[s1])
            {
                string x = x_entry.first;
                lli cost_s1_x = x_entry.second;
                if(direct.count(x) && direct[x].count(s2))
                {
                    lli cost_x_s2 = direct[x][s2];
                    minimal_price = min(minimal_price, cost_s1_x + cost_x_s2);
                }
            }
        }

        ans += price - minimal_price;
    }

    cout << ans << '\n';
    return 0;
}