1

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <cmath>
#include <climits>
#include <sstream>


// Структура для хранения информации о вершине
template<typename T>
struct Vertex {
    double g = std::numeric_limits<double>::max(); // Стоимость пути от начальной вершины до данной
    bool deadend = false;
    T parent = T(); // Родительская вершина в пути
};

// Структура для сравнения вершин в очереди
template<typename T>
struct Compare {
    bool operator()(const std::pair<T, Vertex<T>>& a, const std::pair<T, Vertex<T>>& b) {
        /*if(a.second.g != b.second.g)
            return a.second.g < b.second.g;
        return a.second.edge < b.second.edge;*/
        return a.second.g > b.second.g;
    }
};

// Функция для вычисления эвристической оценки

//int heuristic(char a, char b) {
//    return abs(a - b);
//}

int heuristic(int a, int b) {
    return abs(a - b);
}

template<typename T>
std::vector<T> aStar(std::map<T, std::vector<std::pair<T, double>>>& graph, T start, T goal) {
    std::map<T, Vertex<T>> vertices;
    std::priority_queue<std::pair<T, Vertex<T>>, std::vector<std::pair<T, Vertex<T>>>, Compare<T>> openset;
    //std::vector<T> closedset;
    // Инициализация начальной вершины
    vertices[start].g = 0;
    openset.push({ start, vertices[start] });

    while (!openset.empty()) {
        char current = openset.top().first;
        openset.pop();
        //std::cout << current << '\n';
        //std::cout << current << '\n';

        if (current == goal) {
            std::vector<T> path;
            while (current != T()) {
                path.push_back(current);
                current = vertices[current].parent;
            }
            return path;
        }

        //vertices[current].visited = true;
        //std::cout << "Current vertice: " << current << '\n';
        //std::string ssd_str = "Reachable vertices:";
        //std::stringstream ssd;
        for (auto& neighbor : graph[current]) {

            /*
            double tentative_g = vertices[current].g + neighbor.second;


            if (tentative_g < vertices[next].g) {
                vertices[next].g = tentative_g;
                vertices[next].f = vertices[next].g + heuristic(next, goal);
                vertices[next].parent = current;
                openset.push({ next, vertices[next] });
                ssd << " | " << next << " -> " << "g: " << vertices[next].g << " h: " << heuristic(next, goal) << " f: " << vertices[next].f << " | ";
            }*/
            T next = neighbor.first;

            double tentative_g_score = vertices[current].g + neighbor.second;

            /*T next_vert;
            double min_weight = std::numeric_limits<double>::max();
            if (min_weight < tentative_g_score) {
                real_next = next;

            }*/

            if (tentative_g_score <= vertices[next].g) {
                //std::cout << next << '\n';
                //vertices[next].edge = neighbor.second;
                //std::cout << "next: " << next << " weight: " << tentative_g_score;
                //std::cout << " " << vertices[next].parent << '\n';
                vertices[next].parent = current;
                vertices[next].edge = neighbor.second;
                vertices[next].g = tentative_g_score;
                openset.push({ next, vertices[next] });
            }
            /*if (tentative_g_score == vertices[next].g) {
                std::cout << current << next << '\n';
                std::cout << vertices[next].edge << ' ' << neighbor.second << '\n';
                if (vertices[next].edge > neighbor.second) {
                    vertices[next].parent = next;
                    vertices[next].edge = neighbor.second;
                }
            }*/
        }
        //ssd_str = (ssd_str + ssd.str()).length() > ssd_str.length() ? ssd_str + ssd.str() + '\n' : ssd_str + " None\n";
        //std::cout << ssd_str;

        //std::priority_queue<std::pair<T, Vertex<T>>, std::vector<std::pair<T, Vertex<T>>>, Compare<T>> tmp_pq = pq;
        //std::vector<std::pair<T, Vertex<T>>> vec;
        //while (!tmp_pq.empty()) {
        //    vec.push_back(tmp_pq.top());
        //    tmp_pq.pop();
        //}

        //for (const auto& pair : vec) {
        //    std::cout << "(" << pair.first << ", " << pair.second.f << ")" << std::endl;
        //}
    }
    T current = goal;
    std::vector<T> path;
    while (current != T()) {
        path.push_back(current);
        current = vertices[current].parent;
    }
    return path;
}

template<typename T>
void exec() {
    std::map<T, std::vector<std::pair<T, double>>> graph;
    T start, goal;
    std::cin >> start >> goal;

    T from, to;
    double weight;
    while (std::cin >> from >> to >> weight) {
        graph[from].insert(graph[from].end(), { std::make_pair(to, weight) });
    }

    std::vector<T> path = aStar(graph, start, goal);
    /*for (int i = path.size() - 1; i >= 0; --i) {
        std::cout << path[i];
    }*/
    /*for (const auto& pair : vertices) {
        std::cout << "Vertice: " << pair.first << " Weight: " << pair.second.g << " Prev: " << pair.second.parent << '\n';
    }*/

    /*T current = goal;
    std::vector<T> path;
    while (current != T()) {
        path.push_back(current);
        current = vertices[current].parent;
    }*/

    for (int i = path.size() - 1; i >= 0; --i) {
        std::cout << path[i];
    }

    std::cout << '\n';
}

int main() {
    exec<char>();
    return 0;
}