#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <queue>

using namespace std;

int strToTime(string &s){
    return atoi(s.substr(0,2).c_str())*60 + atoi(s.substr(3,2).c_str());
}

struct edge{
    int cost;
    int start;
    int goal;
    int to;
    bool operator<(const edge &e)const{
        return start>e.start;
    }
};

vector<edge> G[101];

struct Sit{
    int cTime;
    int cost;
    int node;

    bool operator<(const Sit &s)const{
        return cTime>s.cTime;
    }
};

const int INF=1000000000;

int backMinCost(int idx,int sTime,int snode);

queue<Sit> *pprv;
queue<Sit> *nnxt;

int main(){
    pprv=new queue<Sit>();
    nnxt=new queue<Sit>();
    queue<Sit> *prv=new queue<Sit>();
    queue<Sit> *nxt=new queue<Sit>();

    int n;
    while(cin>>n&&n!=0){
        for(int i = 0; i < 101; i++)G[i].clear();
        map<string,vector<pair<int,int> > > startAndFinTimes;
        map<string,int> stationIdx;
        stationIdx["Tokyo"]=0;
        stationIdx["Hakodate"]=1;
        int idx=2;
        for(int i = 0; i < n; i++){
            string st,ft;
            string s1,s2;
            edge e;
            cin>>s1>>st>>s2>>ft>>e.cost;
            e.start=strToTime(st);
            e.goal=strToTime(ft);
            if(stationIdx.find(s1)==stationIdx.end())
                stationIdx[s1]=idx++;
            if(stationIdx.find(s2)==stationIdx.end())
                stationIdx[s2]=idx++;
            e.to=stationIdx[s2];
            G[stationIdx[s1]].push_back(e);
        }
        for(int i = 0; i < 101; i++)sort(G[i].begin(),G[i].end());

        map<int,int> minCosts[2][101];
        for(int i = 0; i < 2; i++){
            Sit ss;
            ss.cost=0;
            ss.cTime=480;
            ss.node=i;
            prv->push(ss);
            minCosts[i][ss.node][ss.cTime]=0;
            while(prv->size()){
                while(prv->size()){
                    Sit s=prv->front();prv->pop();
                    for(int ii = 0; ii < G[s.node].size(); ii++){
                        edge &e=G[s.node][ii];
                        // ÔÍÇñÇñ¬³­ÈÁÄ¢­ÌÅ
                        if(e.start<s.cTime)
                            break;
                        if(e.start>60*18||e.goal>60*18)
                            continue;
                        Sit ns=s;
                        ns.cost+=e.cost;
                        ns.cTime=e.goal;
                        ns.node=e.to;
                        if(minCosts[i][ns.node].find(ns.cTime)!=minCosts[i][ns.node].end()){
                            if(minCosts[i][ns.node][ns.cTime]>ns.cost){
                                minCosts[i][ns.node][ns.cTime]=ns.cost;
                                nxt->push(ns);
                            }
                        }
                        else{
                            minCosts[i][ns.node][ns.cTime]=ns.cost;
                            nxt->push(ns);
                        }
                    }
                }
                swap(prv,nxt);
            }
        }
        int minCost=INF;
        for(int i = 0; i < idx; i++){
            for(map<int,int>::iterator it=minCosts[0][i].begin();it!=minCosts[0][i].end();it++){
                for(map<int,int>::iterator iit=minCosts[1][i].begin();iit!=minCosts[1][i].end();iit++){
                    int sum=it->second+iit->second;
                    int nextStartTime=max(it->first,iit->first)+30;
                    int res=backMinCost(0,nextStartTime,i);
                    int res2=backMinCost(1,nextStartTime,i);
                    if(res!=INF&&res2!=INF){
                        sum+=res+res2;
                        minCost=min(minCost,sum);
                    }
                }
            }
        }
        if(minCost==INF)cout<<0<<endl;
        else cout<<minCost<<endl;
    }
    delete prv;
    delete nxt;
    delete nnxt;
    delete pprv;
    return 0;
}

int backMinCost(int idx,int sTime,int snode){
    map<int,int> d[101];
    Sit ss;
    ss.cost=0;
    ss.node=snode;
    ss.cTime=sTime;
    pprv->push(ss);
    d[snode][ss.cTime]=ss.cost;
    while(pprv->size()){
        while(pprv->size()){
            Sit s=pprv->front();pprv->pop();
            for(int ii = 0; ii < G[s.node].size(); ii++){
                edge &e=G[s.node][ii];
                // ÔÍÇñÇñ¬³­ÈÁÄ¢­ÌÅ
                if(e.start<s.cTime)
                    break;
                if(e.start>60*18||e.goal>60*18)
                    continue;
                Sit ns=s;
                ns.cost+=e.cost;
                ns.cTime=e.goal;
                ns.node=e.to;
                if(d[ns.node].find(ns.cTime)!=d[ns.node].end()){
                    if(d[ns.node][ns.cTime]>ns.cost){
                        d[ns.node][ns.cTime]=ns.cost;
                        nnxt->push(ns);
                    }
                }
                else{
                    d[ns.node][ns.cTime]=ns.cost;
                    nnxt->push(ns);
                }
            }
        }
        swap(pprv,nnxt);
    }
    int res=INF;
    for(map<int,int>::iterator it=d[idx].begin();it!=d[idx].end();it++)
        res=min(res,it->second);
    return res;
}

Measured memory_bytes: 1064