/*
  markers.cpp
  The Mark of a Wizard, MCPC 2012 Problem E
  C++ version by Michael Goldwasser
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

#define MAX_TRIALS 16
#define MAX_EDGES 35
#define MAX_SITES 17
#define MAX_DEGREE 6
#define MAX_PATH 7
void validate(int);     // used only for judging

ifstream fin("markers.in");

int degree[MAX_SITES];
int adj[MAX_SITES][MAX_DEGREE];    // adj[v][j] is the index of the jth neighbor of v
int wgt[MAX_SITES][MAX_DEGREE];    // wgt[v][j] is the distance of edge connecting v to its jth neighbor
int topo[MAX_SITES];
int sp[MAX_SITES];
int n;

int toInt(char c) {
    int k = (c - 'A');
    int answer = (k >= 0 && k <= 25 ? k : 26 + (c-'a'));
    if (answer < 0 || answer >= n)
    cerr << "PROBLEM with neighbor label " << c << endl;
    return answer;
}

void computeTopo() {
    int indeg[n];
    int k(0);
    vector<int> ready;
    for (int v=0; v<n; v++) {
    indeg[v] = 0;
    }

    for (int v=0; v<n; v++)
    for (int j=0; j<degree[v]; j++)
        indeg[adj[v][j]]++;

    for (int v=0; v<n; v++) {
    if (indeg[v] == 0)
        ready.push_back(v);
    }
    while (!ready.empty()) {
    int u = ready[ready.size()-1];
    ready.pop_back();
    topo[k++] = u;
    for (int j=0; j<degree[u]; j++) {
        if (--indeg[adj[u][j]] == 0)
        ready.push_back(adj[u][j]);
    }
    }
    validate(k);   // for judging use only
}

bool isSolution(const set<int>& marked) {
    set<int> good;
    good.insert(n-1);
    for (int k=n-2; k >= 0; k--) {
    int u = topo[k];
    int countgood(0);
    for (int j=0; j<degree[u]; j++) {
        if (good.count(adj[u][j]) == 1 && sp[u] == wgt[u][j] + sp[adj[u][j]])
        countgood++;
    }
    if (countgood >= 1 && (marked.count(u) == 1 || countgood == degree[u]))
        good.insert(u);
    }
    return good.count(0) == 1;
}

int solve(set<int>& marked, int next) {
    if (isSolution(marked))
    return marked.size();
    int best = MAX_PATH;                // this must exist
    if (marked.size() < MAX_PATH - 1)
    for (int j=next; j<n; j++) {
        marked.insert(j);
        best = min(best, solve(marked, j+1));
        marked.erase(j);
    }
    return best;
}

int main() {
    int trial(0);
    while (true) {
    fin >> n;
    if (n==0) break;
    if (++trial > MAX_TRIALS)
        cerr << "PROBLEM with too many data sets" << endl;

    // read input
    for (int i=0; i<n; i++) {
        char c;
        fin >> c;
        int v = toInt(c);
        fin >> degree[v];
        for (int j=0; j < degree[v]; j++) {
        fin >> c;
        adj[v][j] = toInt(c);
        fin >> wgt[v][j];
        }
    }

    // Step 1) compute topo order of DAG
    computeTopo();

    // Step 2) compute shortest path lengths from all vertices to sink
    sp[n-1] = 0;   // the sink
    for (int k=n-2; k>=0; k--) {
        int u = topo[k];
        sp[u] = wgt[u][0] + sp[adj[u][0]];
        for (int j=1; j<degree[u]; j++)
        sp[u] = min(sp[u], wgt[u][j] + sp[adj[u][j]]);
    }
    cout << sp[0];  // print shortest path distance (but no newline)

    // Step 3) try to find solution with at most MAX_PATH - 1 markers
    // (otherwise, certainly exists solution with MAX_PATH markers)
    set<int> marked;
    cout << " " << solve(marked, 0) << endl;
    }
}



// used only for judges
void validate(int k) {
    if (n > MAX_SITES)
    cerr << "PROBLEM with too many vertices" << endl;
    if (k != n)
    cerr << "PROBLEM computing topo" << endl;
    if (topo[n-1] != n-1)
    cerr << "PROBLEM as sink is not unique" << endl;
    int e(0);
    for (int j=0; j<n; j++) {
    e += degree[j];
    if (degree[j] > MAX_DEGREE)
        cerr << "PROBLEM with degree of vertex " << j << endl;
    }
    if (e > MAX_EDGES)
    cerr << "PROBLEM with too many total edges" << endl;

}