A

#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <string>
#include <limits>

//граф - ориентированный
using Graph = std::map<std::pair<char, char>, double>;
using Neighbors = std::map<char, std::vector<char>>;
Graph edges;
Neighbors vertices;

std::vector<char> greedy_alg(char start, char end) {
    std::vector<char> previous;
    std::vector<char> path;
    previous.push_back(start);
    char current = start;
    double inf = std::numeric_limits<double>::infinity();
    double minWeight = inf;
    while(current != end){
        if (vertices[current].empty()) {
            previous.pop_back();
            char tmp = current;
            current = previous[previous.size() - 1];
            vertices[current].erase(std::remove(vertices[current].begin(), vertices[current].end(), tmp), vertices[current].end());
            continue;
        }
        char tmp_v;
        for (const auto& vert : vertices[current]) {
            if (edges[std::make_pair(current, vert)] < minWeight) {
                minWeight = edges[std::make_pair(current, vert)];
                tmp_v = vert;
            }
        }
        previous.push_back(tmp_v);
        minWeight = inf;
        current = previous[previous.size() - 1];
        path.push_back(current);
    }
    return previous;
}

int  main() {
    char start, end;
    std::cin >> start >> end;
    char v_st, v_end;
    double weight;
    while (std::cin >> v_st >> v_end >> weight) {
        edges[std::make_pair(v_st, v_end)] = weight;

        vertices[v_st].insert(vertices[v_st].end(), { v_end });
    }
    std::vector<char> res = greedy_alg(start, end);
    for (const auto& it : res) {
        std::cout << it;
    }
    std::cout << '\n';
    return 0;
}