modified_A

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

// граф - ориентированный
struct Vertex {
    bool visited = false;
    int neighbors_num;
};

std::vector<char> greedy_alg(std::map<char, std::vector<std::pair<char, double>>>& graph, char start, char end) {
    std::vector<char> path = {start};
    std::map<char, Vertex> vertices;
    double inf = std::numeric_limits<double>::max();
    double minWeight = inf;
    char current = start;
    vertices[start].visited = true;
    vertices[start].neighbors_num = graph[current].size();
    while (current != end) {
        if (!vertices[current].visited) {
            vertices[current].neighbors_num = graph[current].size();
            vertices[current].visited = true;
        }
        if (vertices[current].neighbors_num == 0) {
            path.pop_back();
            current = path[path.size() - 1];
        }
        char next;
        for (const auto& vert : graph[current]) {
            if (graph[vert.first].size() == 0 && vert.first != end) {
                vertices[current].neighbors_num--;
                continue;
            }
            else if (graph[vert.first].size() == 0 && vert.first == end) {
                path.push_back(end);
                return path;
            }
            if (vert.second < minWeight && graph[vert.first].size() > 0) {
                minWeight = vert.second;
                next = vert.first;
            }
        }
        path.push_back(next);
        minWeight = inf;
        current = next;

    }
    return path;
}

int main() {
    std::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].insert(graph[from].end(), { std::make_pair(to, weight) });
    }
    std::vector<char> res = greedy_alg(graph, start, end);
    for (const auto& it : res) {
        std::cout << it;
    }
    std::cout << '\n';
    return 0;
}