#include <iostream>

#include <vector>
#include <fstream>

using namespace std;

void travel(int **matrix, const int& n, bool *check, vector<int>& from, const int &d, int td, int index)
{
    check[index] = true;

    if(td > d)
    {
        check[index] = false;
        return;
    }

    if(td == d)
    {
        check[index] = false;
        from.push_back(index);
        return;
    }

    for(int i = 0; i < n; i++)
        if(matrix[index][i] > 0 && !check[i])
            travel(matrix, n, check, from, d, td+matrix[index][i], i);

    check[index] = false;
}



int main()

{
    ifstream fin("cities.dat");
    int test;

    int n, e, d;

    fin >> test;

    for(int a = 0; a < test; a++)
    {
        fin >> n >> e >> d;

        int **matrix = new int*[n];
        vector<char> city;
        for(int i = 0; i < n; i++)
        {
            matrix[i] = new int[n];
            for(int j = 0; j < n; j++)
                matrix[i][j] = 0;
        }

        for(int i = 0; i < e; i++)
        {
            char c1, c2;
            int distance;

            fin >> c1 >> c2 >> distance;
            int index1 = -1, index2 = -1;
            for(int i = 0; i < city.size(); i++)
            {
                if(city[i] == c1)
                    index1 = i;
                else if(city[i] == c2)
                    index2 = i;
            }

            if(index1 < 0)
            {
                city.push_back(c1);
                index1 = city.size()-1;
            }

            if(index2 < 0)
            {
                city.push_back(c2);
                index2 = city.size()-1;
            }

            matrix[index1][index2] = distance;
            matrix[index2][index1] = distance;
        }

        int temp;
        fin >> temp >> temp >> temp;
        cout << endl;
        for(int i = 0; i < city.size(); i++)
        {
            cout << city[i] << " ";
            for(int j = 0; j < n; j++)
                cout << matrix[i][j] << " ";
            cout << endl;
        }

        bool *check = new bool[n];
        for(int i = 0; i < n; i++)
            check[i] = false;

        vector<int> from;

        int start_index;
        for(int i = 0; i < city.size(); i++)
            if(city[i] == 'X')
            {
                start_index = i;
                break;
            }

        travel(matrix, city.size(), check, from, d, 0, start_index);

        if(from.size() != 1)
            cout << "I do not know\n";
        else
            cout << city[from.back()] << endl;

        for(int i = 0; i < n; i++)
            delete [] matrix[i];
        delete [] matrix;
    }


    return 0;

}