#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iterator>
#include <assert.h>
using namespace std;


const string file = "file";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;


struct Node
{
	int floor;
	int x, y;

	Node(int floor, int x, int y)
	{
		this->floor = floor;
		this->x = x;
		this->y = y;
	}
	Node()
	{

	}

};


double euclidDistance(const Node& n1, const Node& n2)
{
	return sqrt( 1.0*(n1.x - n2.x)*(n1.x - n2.x) + (n1.y - n2.y)*(n1.y - n2.y) + 25 * (n1.floor - n2.floor)*(n1.floor - n2.floor));
}


string tostring(int x)
{
	ostringstream ss;
	ss << x;
	return ss.str();
}


string getPath(int a, int b, vector<vector<int> >& recons)
{
	if(a == b)
		return "";
	if(recons[a][b] == -2)
	{
		return "";//to_string(b);
	}
	int next = recons[a][b];


	string left = getPath(a, next, recons);
	string center = tostring(next);
	string right = getPath(next, b, recons);

	if(left.length() == 0 || left.back() != ' ')
	{
		left.push_back(' ');
	}
	if(right.length() == 0 || right.front() != ' ')
	{
		center.push_back(' ');
	}

	return left + center + right;
}






int main()
{
#ifdef ONLINE_JUDGE
	ostream &fout = cout;
	istream &fin = cin;
#else
	fstream fout(outfile.c_str(), ios::out);
	fstream fin(infile.c_str(), ios::in);
#endif	

	int N, M;

	while(fin >> N && fin >> M)
	{
	
		vector<Node> nodes(N);

		vector<vector<double> > RF;
		vector<vector<int> > recons;
		RF.resize(N, vector<double>(N, INF));
		recons.resize(N, vector<int>(N, - 1));
		vector<int> prec(N);
		for(int i = 0; i < N; i++)
		{
			int x, y, z;
			fin >> z >> x >> y;
			nodes[i] = Node(z, x, y);
		}
	
		for(int i = 0; i < M; i++)
		{
			int a, b;
			string s;
			fin >> a >> b;
			fin >> s;
			if(s == "walking")
			{
				RF[a][b] = euclidDistance(nodes[a], nodes[b]);
				RF[b][a] = euclidDistance(nodes[b], nodes[a]);
				recons[a][b] = -2;
				recons[b][a] = -2;
			}
			else if(s == "escalator")
			{
				RF[a][b] = 1;
				RF[b][a] = 3 * euclidDistance(nodes[b], nodes[a]);
				recons[a][b] = -2;
				recons[b][a] = -2;
			}
			else if(s == "lift")
			{
				RF[a][b] = 1;
				RF[b][a] = 1;
				recons[a][b] = -2;
				recons[b][a] = -2;
			}
			else if(s == "stairs")
			{
				RF[a][b] = euclidDistance(nodes[a], nodes[b]);
				RF[b][a] = euclidDistance(nodes[b], nodes[a]);
				recons[a][b] = -2;
				recons[b][a] = -2;
			}
		}


		for(int k = 0; k < N; k++)
		{
			for(int i = 0; i < N; i++)
			{
				for(int j = 0; j < N; j++)
				{
					if(i == j || RF[i][k] == INF || RF[k][j] == INF)
						continue;

					if(RF[i][k] + RF[k][j] < RF[i][j])
					{
						RF[i][j] = RF[i][k] + RF[k][j];
						recons[i][j] = k;
					}
				}
			}
		}


		fin >> M;
		for(int i = 0; i < M; i ++)
		{
			int a, b;
			fin >> a >> b;

			string left = tostring(a);
			string center = getPath(a, b, recons);
			string right = tostring(b);

			if(center.length() != 0 && center.front() == ' ' && center.back() == ' ')
			{

			}
			else if(center.length() != 0 )
			{
				left.push_back(' ');
				center.push_back(' ');
			}
			else
			{
				left.push_back(' ');
			}

			fout << left + center + right << "\n";
		}
		fout << "\n";
	}

#ifdef ONLINE_JUDGE
#else

	fin.close();
	fout.close();
#endif
}