#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include <cmath>
#define N 26
using namespace std;
typedef struct Priority{
    vector<int> resultat;
    double prior;
    double var_evristic;
} Priority;

bool operator < (const Priority &com_ver_1, const Priority &com_ver_2){
    return com_ver_1.prior > com_ver_2.prior;
}

class Graf{
private:
    double **graf;
    int d;
    vector<int> str;
    double weight_from[N];
public:
    Graf(int i, int start): d(i){
        str.push_back(start);
        graf = new double *[d];
        for(int i = 0; i < d; i++)
            graf[i] = new double[d];
        for(int i = 0; i < d; i++){
            for(int j = 0; j < d; j++)
                  graf[i][j] = 0;
        }
    }
    ~Graf(){
            for (int i = 0; i < d; i++)
                delete[] graf[i];
            delete[] graf;
			delete[] weight_from;
            str.clear();
        }
    void matrix(char i, char j, double weight){
        graf[i][j] = weight;
    }
    void Display(){
        for(int i = 0; i < d; i++){
            for(int j = 0; j < d; j++){
                cout << graf[i][j] << " ";
            }
            cout << endl;
        }
    }
    void print_path(int first, int finish){
        bool admissible = 1;
        bool monotonic = 1;
        int i = 0;
        if(str.size() > 1){
        while(str[i] != finish)
        {
            admissible = is_admissible(finish, str[i])  && admissible ? 1 : 0;
            i++;
            monotonic = is_monotonic(finish, str[i-1], str[i]) && monotonic ? 1 : 0;
        }
        admissible = is_admissible(finish, str[i]) && admissible ? 1 : 0;
        for(i = 0; i < str.size() ; i++)
            cout << char(str[i] + 97);
        if(admissible)
            cout<<endl<<"Heuristic is admissible"<<endl;
        else
            cout<<endl<<"Heuristic is not admissible"<<endl;
        if(monotonic)
            cout<<"Heuristic is monotonic"<<endl;
        else
            cout<<"Heuristic is not monotonic"<<endl;
        }
    else cout << "нет пути";
    }
	double evristic(int i, int j){
	    return abs(i - j);
	}
	bool is_admissible( int finish, int ver){
        return weight_from[ver] >= evristic(finish, ver);
    }
    bool is_monotonic(int finish, int ver1, int ver2){
        return weight_from[ver1] - weight_from[ver2] >= evristic(finish, ver1) - evristic(finish, ver2);
    }
    void min_way_A_star(int first, int finish, priority_queue <Priority> &queue, double way){
        vector<int> str1;
        while(true){
            for(int j = 0; j < d; j++)
                if(graf[first][j] != 0){
                    Priority elem;
                    elem.var_evristic = evristic(finish, j);
                    elem.prior = graf[first][j] + way + elem.var_evristic;
                    weight_from[first] = graf[first][j] + way;
                    for(auto i: str1)
                        elem.resultat.push_back(i);
                    elem.resultat.push_back(j);
                    queue.push(elem);
                }
            if(queue.empty())
                break;
            if(!queue.empty()){
                Priority popped;
                popped = queue.top();
                queue.pop();
                first = popped.resultat[popped.resultat.size()-1];
                str1 = popped.resultat;
                way = popped.prior - popped.var_evristic;
            }
            if(str1[str1.size()-1] == finish){
                for(auto i: str1)
                    str.push_back(i);
                break;
            }
        }
		str1.clear();
    }
};

int main() {
    char start, the_end, from, to;
    double weight;
    cin>> start >> the_end;
    priority_queue <Priority> queue;
    Graf matr(N, start - 'a');
    while(cin >> from >> to >> weight){
        matr.matrix(from - 'a', to - 'a', weight);
    }
  //  matr.Display();
    matr.min_way_A_star(start - 'a', the_end - 'a', queue, 0);
    matr.print_path(start - 'a', the_end - 'a');
    return 0;
}