#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;

struct root {
	int start;
	int goal;
	int time;
	vector<int>ways;
	root():ways() {
		start = 0;
		goal = 0;
	}
	root(const int start_, const int goal_, const int time_, const vector<int>ways_)
		:start(start_), goal(goal_), time(time_), ways(ways_) {

	}
};
struct edge {
	int src;
	int dst;
	int cost;
};

struct query {
	int type;
	int id;
	int num;
	int next;
	int nextnext;
	int time;
	query(int type_, int id_, int num_, const int next_,const int nextnext_, int time_) :type(type_), id(id_), num(num_), next(next_),nextnext(nextnext_), time(time_) {

	}
};
class Compare {
public:
	bool operator()(const query&l, const query&r) {
		return l.time==r.time?l.type==r.type?l.nextnext>r.nextnext:l.type<r.type:l.time> r.time;
	}
};	//aa?????????????????¶
struct letter {
	int id;
	string name;
	vector<int>ways;
};
int main() {
	int aa = 0;
	while (1) {
		int N, M; cin >> N >> M;
		if (!N)break;
		if(aa)	cout << endl;

		aa++;
		
		vector<vector<root>>roots(N, vector<root>(N));
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				
				roots[i][j].start = i;
				roots[i][j].goal = j;
				if (i == j) {
					roots[i][j].time = 0;
					roots[i][j].ways = vector<int>{};
				}
				else {
					roots[i][j].time = 1e9;
				}

			}
		}
		for (int i = 0; i < M; ++i) {
			int a, b, c; cin >> a >> b >> c; a--; b--;
			roots[a][b] = root( a,b,c,vector<int>{b} );
			roots[b][a] = root(b, a, c, vector<int>{a});
		}
		for (int k = 0; k < N; ++k) {
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					if (i == k || j == k||i==j)continue;
					if (roots[i][k].time < 1e8&&roots[k][j].time < 1e8) {
						const int  nexttime = roots[i][k].time + roots[k][j].time;
						bool ok = true;
						vector<int>preways(roots[i][j].ways);
						vector<int>nextways(roots[i][k].ways);
						nextways.insert(nextways.end(), roots[k][j].ways.begin(), roots[k][j].ways.end());
						if (nexttime > roots[i][j].time)ok = false;
						else if (nexttime == roots[i][j].time) {

							for (int a= 0; a < preways.size(); ++a) {
								if (preways[a] > nextways[a]) {
									ok = true;
									break;
								}
								else if (preways[a] < nextways[a]) {
									ok = false;
									break;
								}
							}
						}
						else {
							ok = true;
						}
						if (ok) {
							roots[i][j].time = nexttime;
							roots[i][j].ways = nextways;
						}
					}
				}
			}
		}
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (roots[i][j].time < 1e8) {
					roots[i][j].ways.insert(roots[i][j].ways.begin(), i);
					roots[i][j].ways.emplace_back(-1);
				}
			}
		}


		int L; cin >> L;
		priority_queue<query, vector<query>, Compare>que;
		map<int,letter>mp;
		for (int i = 0; i < L; ++i) {
			int a, b, c; string d; cin >> a >> b >> c >> d; a--; b--;
			mp[i] = letter{ i,d,roots[a][b].ways };
			int nextnext = roots[a][b].ways[1];
			que.push(query(1,i,0,roots[a][b].ways[0],nextnext,c ));
		}
		for (int i = 0; i < N; ++i) {
			que.push(query{ 0,0,0,i,0,0 });
		}
		vector<pair< int,string>>anss;
		//vector<vector<vector<int>>>waits(N,vector<vector<int>>(N,vector<int>()));
		vector<deque<vector<tuple<int,int,int>>>>nexts(N);
		vector<int>exists(N);
		
		while (!que.empty()) {
			query q(que.top());
			que.pop();

			const int nowtime = q.time;

			const int nowplace = q.next;
			//??°??£?????????
			if (q.type == 0) {
				assert(exists[nowplace] == false);
				if (!nexts[nowplace].empty()) {
					auto carrys(nexts[nowplace].front());
					const int nextplace = get<2>(carrys[0]);
					for (auto carry : carrys) {
						int aid = get<0>(carry);
						int anum = get<1>(carry);
						const int needtime = roots[nowplace][nextplace].time;
						const int nexttime = nowtime + needtime;
						const int backtime = nexttime + needtime;
						que.push(query(1,aid,anum + 1,nextplace,mp[aid].ways[anum+2],nexttime ));
						exists[nowplace] = false;
					}
					que.push(query(0, 0, 0, nowplace, 0,nowtime+2*roots[nowplace][nextplace].time));
					nexts[nowplace].pop_front();
				}
				else {
					assert(!exists[nowplace]);
					exists[nowplace] = true;
				}
			}
			//???????????\???
			else {
				if (q.nextnext==-1) {
					anss.push_back(make_pair(q.time, mp[q.id].name));
				}
				else {
					const int nextplace = mp[q.id].ways[q.num + 1];
					if (!exists[nowplace]) {
						bool flag = true;
						for (int i = 0; i < nexts[nowplace].size(); ++i) {
							if (get<2>(nexts[nowplace][i][0]) == nextplace) {
								nexts[nowplace][i].push_back(make_tuple(q.id, q.num, nextplace));
								flag = false;
								break;
							}
						}
						if (flag) {
							nexts[nowplace].push_back(vector<tuple<int,int,int>>(1, make_tuple(q.id, q.num, nextplace)));
						}
					}
					else {
						bool flag = true;
						for (int i = 0; i < nexts[nowplace].size(); ++i) {
							if (get<2>(nexts[nowplace][i][0]) == nextplace) {
								nexts[nowplace][i].push_back(make_tuple(q.id, q.num, nextplace));
								flag = false;
								break;
							}
						}
						if (flag) {
							nexts[nowplace].push_back(vector<tuple<int, int, int>>(1, make_tuple(q.id, q.num, nextplace)));
						}
						que.push(query(0, 0, 0, nowplace, 0, nowtime));
						exists[nowplace] = false;

					}
				}
				
			}
		}
		sort(anss.begin(), anss.end());
		for (auto ans : anss) {
			cout << ans.second << " " << ans.first << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3452