#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const db INF = 1e18;

template<typename T>
void updMin(T& a, T b)
{
	a = min(a, b);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	VI z(n), x(n), y(n);
	vector d(n, vector<db>(n, INF));
	vector mid(n, VI(n, -1));
	FOR(i, 0, n)
	{
		cin >> z[i] >> x[i] >> y[i];
	}
	FOR(i, 0, n)
		d[i][i] = 0;
	while (m--)
	{
		int u, v;
		string s;
		cin >> u >> v >> s;
		db dist = hypot(x[v] - x[u], y[v] - y[u], 5 * (z[v] - z[u]));
		if (s[0] == 'w' || s[0] == 's')
		{
			updMin(d[u][v], dist);
			updMin(d[v][u], dist);
		}
		else if (s[0] == 'l')
		{
			updMin(d[u][v], 1.0);
			updMin(d[v][u], 1.0);
		}
		else
		{
			assert(s[0] == 'e');
			updMin(d[u][v], 1.0);
			updMin(d[v][u], 3 * dist);
		}
	}
	FOR(k, 0, n)
	{
		FOR(i, 0, n)
		{
			FOR(j, 0, n)
			{
				db dikj = d[i][k] + d[k][j];
				if (dikj < d[i][j])
				{
					d[i][j] = dikj;
					mid[i][j] = k;
				}
			}
		}
	}
	function<void(int, int)> printPath = [&](int u, int v)
	{
		if (u == v)
			return;
		if (mid[u][v] == -1)
		{
			cout << u << " ";
			return;
		}
		printPath(u, mid[u][v]);
		printPath(mid[u][v], v);
	};
	int q;
	cin >> q;
	while (q--)
	{
		int u, v;
		cin >> u >> v;
		printPath(u, v);
		cout << v << "\n";
	}
	return 0;
}