http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2750
//1868088 2009-05-14 08:38:13 Wrong Answer  2750 C++ 130 4100 aslys 
//1868170 2009-05-14 09:46:00 Time Limit Exceeded  2750 C++ 1001 4100 aslys 
//1868224 2009-05-14 10:24:24 Accepted  2750 C++ 150 4112 aslys 
#include<iostream>
#include<string>
#include<queue>
using namespace std;

const int inf = 1000000000;
const int N = 1001;
struct Node
{
    int t;
    char s[5];
    char e[5];
}pt[N];
struct node
{
    int v;
    int cost;
    node(){}//定義中間變量時，要用到該析構函數，此時不需要初值
    node(int a,int c)
    {
        v = a;
        cost = c;
    }
    friend bool operator <(node a,node b) //重載運算符，從小到大排序
    {
        return a.cost > b.cost;
    }
};    
int n,gra[N][N];

void dijkstra(int u)
{
    priority_queue<node>Q;
    node p,q;
    bool mark[N];
    int dist[N];
    int i,j,index;
    for(i=1;i<=n;i++)
    {
        if(gra[u][i] != inf)
        {
            p.v = i;
            p.cost = gra[u][i];
            Q.push(p);
        }
        dist[i] = gra[u][i];
        mark[i] = 0;
    }
    mark[u] = 1;
    for(i=1;i<=n;i++)
    {
        index = -1;
        while(!Q.empty()) //對頭元素就是最小的
        {
            q = Q.top();
            Q.pop();
            if(mark[q.v] == 0)
            {
                index = q.v;
                break ;
            }
        }
        if(index == -1)
            break;
        if(index == n)
            break;
        mark[index] = 1;

        for(j=1;j<=n;j++)
            if(mark[j] == 0 && dist[j] > q.cost + gra[index][j])
            {
                dist[j] = q.cost + gra[index][j];
                p.cost = dist[j];
                p.v = j;
                Q.push(p);
            }
    }
    if(dist[n] == inf)
        printf("-1\n");
    else
        printf("%d\n",dist[n]);
}
int main()
{    

    while(cin>>n && n)
    {
        char temp[N];
        int i,j,len;
        for(i=1;i<=n;i++)//init()
            for(j=1;j<=n;j++)
                gra[i][j] = inf;

        for(i=1;i<=n;i++)
        {
            scanf("%d%s",&pt[i].t,temp);

            len = strlen(temp);

            for(j=0;j<4;j++)//取頭
                pt[i].s[j] = temp[j];
            pt[i].s[j] = '\0';

            len -= 4;
            for(j=0;j<4;j++)//取尾
                pt[i].e[j] = temp[j+len];
            pt[i].e[j] = '\0';
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(strcmp(pt[i].e,pt[j].s) == 0)
                    gra[i][j] = pt[i].t;
        dijkstra(1);
    }
    return 0;
}