#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#define PI acos(-1.0)#define max(a,b) (a)>(b)? (a):(b)#define min(a,b) (a)>(b)? (b):(a)#define INT_MIN -0x7FFFFFFF#define INT_MAX 0x7FFFFFFFint n;struct node{ char f[10],b[10]; int t;}no[1010];int map[1010][1010];int time[1010];int s[1010];int main(){ int i,j,k; char str[100]; while(scanf("%d",&n),n) { int tt; for(i=0;i<n;i++) { scanf("%d%s",&tt,str); int len=strlen(str); no[i].t=tt; for(j=0;j<4;j++) no[i].f[j]=str[j]; no[i].f[4]=' '; for(j=0;j<4;j++) no[i].b[j]=str[len-4+j]; no[i].b[4]=' '; } for(i=0;i<=n;i++) for(j=0;j<=n;j++) map[i][j]=INT_MAX; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(i==j) continue; if(strcmp(no[i].b,no[j].f)==0) { map[i][j]=no[i].t; } } } for(i=0;i<n;i++) time[i]=map[0][i]; memset(s,0,sizeof(s)); s[0]=1; time[0]=0; for(i=0;i<n-1;i++) { int mi=INT_MAX; int ar; for(j=0;j<n;j++) { if(!s[j] && mi>time[j]) { ar=j; mi=time[j]; } } s[ar]=1; for(k=0;k<n;k++) { if(!s[k] && map[ar][k]<INT_MAX && time[k]>time[ar]+map[ar][k]) { time[k]=time[ar]+map[ar][k]; } } } if(time[n-1]==INT_MAX) { printf("-1n"); } else printf("%dn",time[n-1]); } return 0;}
