A*_1

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

std::vector<char> greedy_alg(std::unordered_map<char, std::vector<std::pair<char, double>>>& graph, char start, char end) {
    std::vector<char> path = { start };
    std::unordered_map<char, std::pair<bool, int>> vertices;
    double inf = std::numeric_limits<double>::infinity();
    double minWeight = inf;
    char current = start;
    vertices[start] = { true, graph[current].size() };
    while (!path.empty() && current != end) {
        auto& vertex = vertices[current];
        if (!vertex.first) {
            vertex.second = graph[current].size();
            vertex.first = true;
        }
        if (vertex.second == 0) {
            path.pop_back();
            if (!path.empty()) {
                current = path.back();
            }
            continue;
        }
        int tmp;
        char next;
        for (const auto& vert : graph[current]) {
            tmp = !vertices[vert.first].first ? graph[vert.first].size() : vertices[vert.first].second;
            if (vert.second < minWeight && tmp > 0) {
                minWeight = vert.second;
                next = vert.first;
            }
            if (vert.second < minWeight && tmp == 0 && vert.first != end) {
                vertex.second--;
                continue;
            }
            if (vert.second < minWeight && vert.first == end) {
                path.push_back(end);
                return path;
            }
        }
        //std::cout << current << ' ' << vertex.second << '\n';
        path.push_back(next);
        minWeight = inf;
        current = next;
    }
    return path;
}

int main() {
    std::unordered_map<char, std::vector<std::pair<char, double>>> graph;
    char start, end;
    std::cin >> start >> end;
    char from, to;
    double weight;

    while (std::cin >> from >> to >> weight) {
        graph[from].emplace_back(to, weight);
    }
    std::vector<char> res = greedy_alg(graph, start, end);
    for (const auto& it : res) {
        std::cout << it;
    }
    std::cout << '\n';
    return 0;
}