#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <deque>
#include <string>
#include <unordered_map>
#include <cstdio>

using namespace std;

const int INF = 2e9;

long long sum = 0;

vector<int> used;

vector<pair<pair<int, int>, int>> answer;

void dfs(vector<vector<pair<int, int>>>& pr, vector<vector<int>>& dp, vector<vector<pair<int, char>>>& g, vector<pair<int, char>>& obr, vector<vector<int>>& tok, int now) {
    for (auto next : g[now]) {
        if (dp[now][next.first] == INF) {
            sum = 1e18;
            return;
        } else {
            if (used[next.first] == 1) {
                int r = pr[now][next.first].second;
                int l = pr[now][next.first].first;
                sum += dp[now][next.first];
                answer.push_back({{l, r}, tok[now][next.first]});
                while (r >= now) {
                    used[r] = 0;
                    r = obr[r].first;
                }
            }
            dfs(pr, dp, g, obr, tok, next.first);
        }
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    unordered_map <string, int> kl;
    unordered_map <string, int> num;
    int n, m, t;
    cin >> n >> m >> t;
    vector<vector<pair<int, char>>> g(n + 1);
    vector<pair<int, char>> obr(n + 1);
    for (int i = 2; i <= n; ++i) {
        int x;
        char c;
        cin >> x >> c;
        g[x].push_back({ i, c });
        obr[i].first = x;
        obr[i].second = c;
    }
    vector<vector<int>> heig;
    heig.reserve(1000);
    for (int i = 1; i <= n; ++i) {
        if (g[i].size() == 0) {
            int h = 0;
            int now = i;
            while (now != 1) {
                now = obr[now].first;
                h++;
            }
            while (heig.size() <= h) {
                heig.push_back({});
            }
            heig[h].push_back(i);
        }
    }
    vector<string> merd(m);
    vector<string> mer;
    mer.reserve(100000);
    for (int i = 0; i < m; ++i) {
        int x;
        string s;
        cin >> x >> s;
        merd[i] = s;
        if (kl[s] != 0 && x < kl[s]) {
            kl[s] = x;
            num[s] = i + 1;
        } else {
            kl[s] = x;
            num[s] = i + 1;
        }
    }
    sort(merd.begin(), merd.end());
    mer.push_back(merd[0]);
    for (int i = 1; i < merd.size(); ++i) {
        if (mer.back() != merd[i]) {
            mer.push_back(merd[i]);
        }
    }
    vector<vector<pair<int, int>>> pr(n + 1, vector<pair<int, int>> (n + 1));
    vector<vector<int>> tok(n + 1, vector<int> (n + 1));
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
    vector<int> start;
    for (int i = heig.size() - 1; i > 0; --i) {
        for (int l = 0; l < heig[i].size(); ++l) {
            start.push_back(heig[i][l]);
        }
        for (int j = 0; j < start.size(); ++j) {
            string s;
            int now = start[j];
            deque<int> d;
            for (int q = 0; q < i; ++q) {
                s = obr[now].second + s;
                d.push_front(now);
                now = obr[now].first;
            }
            d.push_front(now);
            auto it_1 = lower_bound(mer.begin(), mer.end(), s), it_2 = upper_bound(mer.begin(), mer.end(), s);
            if (it_1 != mer.end() && it_1 == --it_2) {
                for (int c = 0; c < d.size() - 1; ++c) {
                    if (kl[*it_1] < dp[d[c]][d[c + 1]]) {
                        pr[d[c]][d[c + 1]].first = d.front();
                        pr[d[c]][d[c + 1]].second = d.back();
                        dp[d[c]][d[c + 1]] = kl[*it_1];
                        tok[d[c]][d[c + 1]] = num[*it_1];
                    }
                }
            }

            while (d[0] != 1) {
                s.pop_back();
                s = obr[now].second + s;
                d.pop_back();
                now = obr[now].first;
                d.push_front(now);
                auto it_1 = lower_bound(mer.begin(), mer.end(), s), it_2 = upper_bound(mer.begin(), mer.end(), s);
                if (it_1 != mer.end() && it_1 == --it_2) {
                    for (int c = 0; c < d.size() - 1; ++c) {
                        if (kl[*it_1] < dp[d[c]][d[c + 1]]) {
                            pr[d[c]][d[c + 1]].first = d.front();
                            pr[d[c]][d[c + 1]].second = d.back();
                            dp[d[c]][d[c + 1]] = kl[*it_1];
                            tok[d[c]][d[c + 1]] = num[*it_1];
                        }
                    }
                }
            }
        }
    }
    used.resize(n + 1, 1);
    dfs(pr, dp, g, obr, tok, 1);
    if (sum > 1e17) {
        cout << -1;
    } else {
        cout << sum;
        if (t == 1) {
            cout << "\n" << answer.size() << "\n";
            for (int i  = 0; i < answer.size(); ++i) {
                cout << answer[i].first.first << " " << answer[i].first.second << " " << answer[i].second << "\n";
            }
        }
    }

    return 0;
}