A*_2

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


// Структура для хранения информации о вершине
template<typename T>
struct Vertex {
    double g = 0; // Стоимость пути от начальной вершины до данной
    double f = 0; // Общая стоимость пути (g + h)
    double visited = false;
    T parent; // Родительская вершина в пути
};

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

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

//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;
    vertices[start].f = vertices[start].g + heuristic(start, goal);
    vertices[start].parent = T();
    openset.push({ start, vertices[start] });

    while (!openset.empty()) {
        char current = openset.top().first;
        openset.pop();
        //closedset.push_back(current);
        vertices[current].visited = true;
        //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;

            if (vertices[next].visited == true && tentative_g_score >= vertices[next].g) {
                continue;
            }
            if (vertices[next].visited == false || tentative_g_score < vertices[next].g) {
                //std::cout << next << '\n';
                vertices[next].parent = current;
                vertices[next].g = tentative_g_score;
                vertices[next].f = vertices[next].g + heuristic(next, goal);
                if (!vertices[next].visited) {
                    vertices[next].visited = true;
                    openset.push({ next, vertices[next] });
                }
            }
        }
        //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;
        //}
    }
}

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];
    }
    std::cout << '\n';
}

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