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)
    
{
        
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;
}