struct dat{
    string s;
    int val;
    string out;
    dat() {}
    dat(string& a, int b, string p){
        this->s = a;
        this->val = b;
        this->out = p + ";" + this->s;
    }
    bool operator <(const dat& a)const{
        return val > a.val
            || (val == a.val && out > a.out);
    }
};

inline void chuanhoa(string& s){
    for(int i = 0; i < s.size(); ++i){
        if(i == 0 || s[i - 1] == ' '){
            if('a' <= s[i] && s[i] <= 'z') s[i] += 'A' - 'a';
        }
        else if('A' <= s[i] && s[i] <= 'Z') s[i] += 'a' - 'A';
    }
}

std::string travelPath(std::string x, std::string y, std::vector<std::vector<std::string>> paths)
{
    map<string, vector< pair<string, int> > > ke;
    for(auto i : paths){
        chuanhoa(i[0]);
        chuanhoa(i[1]);
        ke[i[0]].push_back({i[1], stoi(i[2])});
        ke[i[1]].push_back({i[0], stoi(i[2])});
    }
    priority_queue<dat, vector<dat> > open;
    open.push(dat(x, 0, ""));
    while(open.size()){
        auto c = open.top();
        open.pop();
        if(c.s == y){
            return c.out.substr(1, c.out.size() - 1);
            continue;
        }
        for(auto i : ke[c.s]){
            open.push(dat(i.first, c.val + i.second, c.out));
        }
    }
}