#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
//#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define BIG_NUM INT_MAX
#define NUM 32
#define SIZE 1000

enum Type{
	Human,
	Letter,
};

struct Edge{
	Edge(int arg_to,int arg_dist){
		to = arg_to;
		dist = arg_dist;
	}
	int to,dist;
};

struct Porter{
	int home_office;
	vector<int> Bag;
};

struct Item{
	string name;
	int final_office;
};

struct Data{
	Data(int arg_item_id,int arg_arrive_time,int arg_next_loc){
		item_id = arg_item_id;
		arrive_time = arg_arrive_time;
		next_loc = arg_next_loc;
	}
	bool operator<(const struct Data& arg) const{
		if(arrive_time != arg.arrive_time){
			return arrive_time < arg.arrive_time;
		}else{
			return next_loc < arg.next_loc;
		}
	}
	int item_id,arrive_time,next_loc;
};

struct Office{
	bool can_port;
	int pre_time; //ポーターが前回帰ってきた時刻
	vector<Data> V;
};

struct Info{
	Info(Type arg_type,int arg_time,int arg_id,int arg_arrive_loc){
		type = arg_type;
		time = arg_time;
		id = arg_id;
		arrive_loc = arg_arrive_loc;
	}
	bool operator<(const struct Info &arg) const{ //時刻の昇順(PQ)
		return time > arg.time;
	}
	Type type;
	int time,id,arrive_loc;
};

struct FINISH{
	FINISH(string arg_name,int arg_time){
		name = arg_name;
		time = arg_time;
	}
	bool operator<(const struct FINISH &arg) const{
		if(time != arg.time){ //時刻または名前の昇順(PQ)
			return time > arg.time;
		}else{
			return name > arg.name;
		}
	}
	string name;
	int time;
};

int N,E;
int min_dist[NUM][NUM];
int next_table[NUM][NUM];
int num_item;
vector<Edge> G[NUM];
Office office[NUM];
Porter porter[NUM];
Item item[SIZE];
priority_queue<Info> EVENT;
priority_queue<FINISH> ANS;
int case_num;


//転送先へ最短経路で届ける際の、次の中継点を求める
int find_next(int current,int goal){

	int minimum = min_dist[current][goal],min_index = BIG_NUM,mid;

	for(int i = 0; i < G[current].size(); i++){
		mid = G[current][i].to;
		if(G[current][i].dist+min_dist[mid][goal] != minimum)continue;

		min_index = min(min_index,mid);
	}

	return min_index;
}

//bool DEBUG = false;

void func(){

	if(case_num > 0)printf("\n");

	for(int i = 0; i < N; i++){
		G[i].clear();
		office[i].V.clear();
		porter[i].Bag.clear();
	}

	while(!EVENT.empty())EVENT.pop();

	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			if(i != k){
				min_dist[i][k] = BIG_NUM;
			}else{
				min_dist[i][k] = 0;
			}
		}
	}

	int from,to,dist;

	for(int loop = 0; loop < E; loop++){

		scanf("%d %d %d",&from,&to,&dist);
		from--;
		to--;

		min_dist[from][to] = dist;
		min_dist[to][from] = dist;

		G[from].push_back(Edge(to,dist));
		G[to].push_back(Edge(from,dist));
	}

	//全点対間最短経路
	for(int mid = 0; mid < N; mid++){
		for(int start = 0; start < N; start++){
			if(min_dist[start][mid] == BIG_NUM)continue;
			for(int goal = 0; goal < N; goal++){
				if(min_dist[mid][goal] == BIG_NUM)continue;
				min_dist[start][goal] = min(min_dist[start][goal],min_dist[start][mid]+min_dist[mid][goal]);
			}
		}
	}

	for(int a = 0; a < N; a++){
		for(int b = 0; b < N; b++){
			if(a == b)continue;
			next_table[a][b] = find_next(a,b);
		}
	}

	scanf("%d",&num_item);

	int tmp_time;

	for(int i = 0; i < num_item; i++){

		cin >> from >> to >> tmp_time >> item[i].name;

		from--;
		to--;

		item[i].final_office = to;

		EVENT.push(Info(Letter,tmp_time,i,from));
	}

	//配達人を、自分の本拠地に配置する
	for(int i = 0; i < N; i++){

		porter[i].home_office = i;

		office[i].can_port = true;
		office[i].pre_time = 0;
	}

	int current_time,tmp_id,tmp_loc,letter_id,tmp_next_loc;

	int num_finish = 0;
	vector<Data> work;

	while(!EVENT.empty()){

		current_time = EVENT.top().time;

		//同時刻のイベントを同時に処理する
		while(EVENT.empty() == false && EVENT.top().time == current_time){

			if(EVENT.top().type == Human){

				tmp_id = EVENT.top().id;

				if(porter[tmp_id].home_office == EVENT.top().arrive_loc){ //本拠地に戻った場合

					office[porter[tmp_id].home_office].can_port = true;
					office[porter[tmp_id].home_office].pre_time = EVENT.top().time; //戻った時刻を記録

				}else{ //別のofficeに到着した場合[★荷物を渡す★]

					tmp_loc = EVENT.top().arrive_loc;
					tmp_time = EVENT.top().time;

					for(int i = 0; i < porter[tmp_id].Bag.size(); i++){

						letter_id = porter[tmp_id].Bag[i];

						if(item[letter_id].final_office == tmp_loc){ //★最終目的地に届いた場合

							num_finish++;

							ANS.push(FINISH(item[letter_id].name,tmp_time));
							if(num_finish == num_item)break;

							continue;
						}

						//次の転送先を先に計算しておく
						tmp_next_loc = next_table[tmp_loc][item[letter_id].final_office];
						if(tmp_next_loc == tmp_loc){
							printf("BUGG!!\n");
							return;
						}

						office[tmp_loc].V.push_back(Data(letter_id,tmp_time,tmp_next_loc));
					}
					porter[tmp_id].Bag.clear();
					if(num_finish == num_item)break;

					//★porterが本拠地に戻る★
					EVENT.push(Info(Human,tmp_time+min_dist[tmp_loc][porter[tmp_id].home_office],tmp_id,porter[tmp_id].home_office));
				}

			}else{

				letter_id = EVENT.top().id;
				tmp_loc = EVENT.top().arrive_loc;
				tmp_time = EVENT.top().time;

				//転送先を計算
				tmp_next_loc = next_table[tmp_loc][item[letter_id].final_office];
				office[tmp_loc].V.push_back(Data(letter_id,tmp_time,tmp_next_loc));
			}

			EVENT.pop();
		}
		if(num_finish == num_item)break;

		//home_officeにいるporterがいたら、Letterを持ち出す

		int min_time,min_next;

		for(int i = 0; i < N; i++){
			if(office[i].can_port == false || office[i].V.size() == 0)continue;

			/*
			 *最も早く、officeに届いた郵便物を探す。
			 *複数あるなら、届先の番号が若い順
			 */

			sort(office[i].V.begin(),office[i].V.end());

			min_time = office[i].V[0].arrive_time; //★到着が早い順にpushされているはず★
			min_next = office[i].V[0].next_loc;

			for(int k = 1; k < office[i].V.size(); k++){
				if(min_time < office[i].V[k].arrive_time)break;
				if(min_time == office[i].V[k].arrive_time){
					min_next = min(min_next,office[i].V[k].next_loc);
				}
			}

			//届先がmin_nextのletterを、porterに持たせる。porterは出発させる
			for(int k = 0; k < office[i].V.size(); k++){

				if(office[i].V[k].next_loc == min_next){ //ポーターのバッグに詰める

					porter[i].Bag.push_back(office[i].V[k].item_id);

				}else{ //今回は運ばない

					work.push_back(office[i].V[k]);
				}
			}
			office[i].V.clear();

			if(work.size() > 0){

				for(int k = 0; k < work.size(); k++){
					office[i].V.push_back(work[k]);
				}
				work.clear();
			}
			//ポーターの移動
			office[i].can_port = false;

			if(office[i].pre_time <= min_time){ //★porterが待つ場合

				EVENT.push(Info(Human,min_time+min_dist[i][min_next],i,min_next));

			}else{ //★porterが待たない場合

				EVENT.push(Info(Human,office[i].pre_time+min_dist[i][min_next],i,min_next));
			}
		}
	}

	while(!ANS.empty()){

		printf("%s %d\n",ANS.top().name.c_str(),ANS.top().time);
		ANS.pop();
	}

	case_num++;
}

int main(){

	case_num = 0;

	while(true){

		//if(DEBUG)break;

		scanf("%d %d",&N,&E);
		if(N == 0 && E == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 3488