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

template<typename T>
std::vector<T> greedy_alg(std::map<T, std::vector<std::pair<T, double>>>& graph, T start, T end) {
    std::vector<T> path = { start };
    std::map<T, std::pair<bool, int>> vertices; // словарь, хранящий информацию о том, посещалась ли это вершина и в какое количество вершин из нее можно перейти
    double inf = std::numeric_limits<double>::max();
    double minWeight = inf; 
    int current = start;
    vertices[start] = { true, graph[current].size() };
    while (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;
        std::string str = "Possible paths:";
        std::string d = "Deadends:";
        std::stringstream out;
        std::stringstream ssd;
        std::cout << "Current vertice: " << current << '\n';
        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--;
                ssd << ' ' << vert.first;
                continue;
            }
            if (vert.second < minWeight && vert.first == end) { // дошли до конца
                path.push_back(end);
                return path;
            }
            out << " | " << current << "-" << vert.first << ": " << vert.second << "(weight) | ";
        }
        str = (str + out.str()).length() > str.length() ? str + out.str() : str + " None";
        std::cout << str << '\n';
        d = (d + ssd.str()).length() > d.length() ? d + ssd.str() + '\n' : "";
        std::cout << d;
        path.push_back(next);
        minWeight = inf;
        current = next;
    }
    return path;
}

int main() {
    std::map<int, std::vector<std::pair<int, double>>> graph;
    int 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<int> res = greedy_alg(graph, start, end);
    std::cout << "Path: ";
    for (const auto& it : res) {
        std::cout << it;
    }
    std::cout << '\n';
    return 0;
}